2020 直播获奖 · 方案二桶计数

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

分数只有 601 种，从 600 往下累加人数

2020
排序

正文

// CSP-J 2020 复赛 T2 · 直播获奖（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2020B
//
// 方案二 · 桶计数（用「分数很小」这个隐含条件）
// 成绩是不超过 600 的非负整数 —— 取值只有 601 种。
// 那就别排序了，开一个 cnt[0..600] 记每个分数出现了几次。
// 每评出一个成绩就 ++ 对应桶，然后从 600 往 0 累加人数，
// 累加到不低于 k 的那个分数，就是这一轮的分数线。
// 每轮最多扫 601 个桶，总复杂度 O(601 * n)，1e5 也稳过。

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

int cnt[605];

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

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

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;

        int k = max(1, i * w / 100);
        int rest = k;
        for (int s = 600; s >= 0; s--) {
            rest -= cnt[s];
            if (rest <= 0) {
                cout << s << (i == n ? '\n' : ' ');
                break;
            }
        }
    }
    return 0;
}

2020 直播获奖 · 方案二 桶计数

正文

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

2020 直播获奖 · 方案二桶计数