直播获奖 CSP-J 2020 T2

题目描述

NOI2130 即将举行。

为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。

本次竞赛的获奖率为 w%，即当前排名前 w%的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 p个选手的成绩，则当前计划获奖人数为 max(1,⌊𝑝×𝑤%⌋)，其中 𝑤是获奖百分比，⌊𝑥⌋表示对 𝑥向下取整，max(𝑥,𝑦)表示 𝑥和𝑦中较大的数。

如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

输入格式

第 1行两个正整数 𝑛,𝑤。分别代表选手总数与获奖率。

第 2行有𝑛个非负整数，依次代表逐一评出的选手成绩。

输出格式

只有一行，包含𝑛个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

输入样例：

10 60
200 300 400 500 600 600 0 300 200 100

输出样例：

200 300 400 400 400 500 400 400 300 300

对顶堆做法 $O(nlogn)$

观察数据不难看出，其实本题是要求动态维护第max(1,⌊𝑝×𝑤%⌋)大的数，因此想到用对顶堆。具体做法是开一个大根堆与一个小根堆，根据每次输入数的大小分情况插入大小根堆，最后动态维护第max(1,⌊𝑝×𝑤%⌋)大的数。具体代码如下：

注：由于本题大小根堆的堆顶最多只会左右移一个单位，因此考虑到用此种方法。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

priority_queue <int> l; // 大根堆
priority_queue <int, vector<int>, greater<int>> r; // 小根堆

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(r.empty() || x > r.top()) r.push(x); // 分情况插入大小根堆
        else l.push(x);

        int t = max(1, i * w / 100); // 动态调整
        if(r.size() > t){
            l.push(r.top()); r.pop();
        }else if(r.size() < t){
            r.push(l.top()); l.pop();
        } 

        cout << r.top() << " ";
    }

    return 0;
}

正解：计数排序 $O(n)$

注：本题时间复杂度确切而言为$O(600n)$

由于本题特性，每个选手的成绩均为不超过 600 的非负整数，因此考虑到通过计数排序插入元素，再通过暴力枚举600次，直到录取人数达到要求。具体代码如下：

注：观察本题数据特点可联想到相应算法。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 610;
int n, w;
int b[N]; // 相当于N个桶

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        b[x] ++; // 排序的核心
        int t = max(1, i * w / 100);
        int cnt = 0;
        for(int j = 600; j >= 0; j--){ // 暴力枚举
            cnt += b[j];
            if(cnt >= t){ // 找到答案即刻返回，避免不必要的枚举
                cout << j << " ";
                break;
            }
        }
    }

    return 0;
}