前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【小码匠自习室】[NOI Online 2020-2 入门组] 未了:可恶的精度会让你焦头烂额

【小码匠自习室】[NOI Online 2020-2 入门组] 未了:可恶的精度会让你焦头烂额

作者头像
小码匠
发布2022-08-08 13:04:38
2010
发布2022-08-08 13:04:38
举报
文章被收录于专栏:小码匠和老码农

碎碎念

  • 当你妄想将几个除不尽后又四舍五入过的小数加在一起打算充当分配律用时,那么,这将是一个悲伤的故事,因为可恶的精度会让你焦头烂额……

标签

  • 贪心、二分查找

题目地址

  • [NOI Online #2 入门组] 未了
    • https://www.luogu.com.cn/problem/P6473

题目描述

输入格式

第一行三个整数 n,L,v 分别表示魔法的种类数,山坡的长度,Sisyphus 的速度。

第二行 n 个整数。第 i 个整数 a_i 表示第 i 个魔法作用的位置。(1<i<n)

第三行一个整数 q 表示宙斯的询问个数。

接下来 q 行每行一个整数,第 i 行的整数 t_i 表示宙斯的第 i 个询问。(1<i<n)

输出格式

输出 q 行,每行恰好一个整数,第 i行的整数对应第 i 个询问的答案。(1≤iq)

如果宙斯无论如何都不能使 Sisyphus 使用的年数大于 t_i ,请输出 −1。

输入输出样例

输入 #1

代码语言:javascript
复制
3 6 3
3 5 1
4
1
3
4
5

输出 #1

代码语言:javascript
复制
0
1
2
-1

说明/提示

题解

小码匠题解一

  • 一次AC
代码语言:javascript
复制
void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, l;
    double v;
    cin >> n >> l >> v;
    vector<double> a(n);
    vector<double> b(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end(), greater<int>());
    
    b[0] = a[0] / v;
    for(int i = 1 ; i < n; ++i) {
        a[i] += a[i - 1];
        b[i] = a[i] / v;
    }
    
    int q, t;
    cin >> q;
    double T = l / v;
    int cnt;
    for(int i = 0; i < q; ++i) {
        cin >> t;
        if(T > t) {
            cout << 0 << endl;
        } else {
            cnt = upper_bound(b.begin(), b.end(), t - T) - b.begin();
            if (cnt >= n) {
                cout << -1 << endl;
            } else {
                cout << cnt + 1 << endl;
            }
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-06-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小码匠和老码农 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 标签
  • 题目地址
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
  • 说明/提示
  • 题解
    • 小码匠题解一
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档