2020 直播获奖 · 方案一每轮排序

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 873 字

每评出一个成绩就排一次序取第 k 名

2020
排序

正文

// CSP-J 2020 复赛 T2 · 直播获奖
// 原题：https://oj.yecheng.tv/p/CSPJ2020B
// 题意：每评出一个成绩就直播一次分数线。第 p 个成绩出来后，
// 计划获奖人数 k = max(1, floor(p * w / 100))，分数线就是当前第 k 名的成绩
// （成绩并列的人都能获奖，所以实际人数可能更多，但分数线仍由第 k 名决定）。
//
// 方案一 · 每轮排一次序（直观，n 大时会超时）
// 把已经评出的成绩拷一份、从大到小排序，取第 k 个输出。
// 每轮都要排序，总复杂度 O(n^2 log n)，只有 n 很小时才来得及。
// 另一个坑：k 必须用整数运算算（p * w / 100），
// 用浮点数存 w% 再乘会出现 2.999999 这类误差，向下取整后结果就错了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("live.in", "r", stdin);
    freopen("live.out", "w", stdout);

    int n, w;
    cin >> n >> w;

    vector<int> a;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
        vector<int> b = a;
        sort(b.begin(), b.end(), greater<int>());
        int k = max(1, i * w / 100);       // 全程整数运算，避开浮点误差
        cout << b[k - 1] << (i == n ? '\n' : ' ');
    }
    return 0;
}

2020 直播获奖 · 方案一 每轮排序

正文

CSP-J 标程 · 复赛真题的其它内容

2020 直播获奖 · 方案一每轮排序