题解：P7072 [CSP-J2020] 直播获奖

Jayfeather2012 · 2024-12-26 13:48:21 · 题解

思路

先把每个选手排序，根据给定人数遍历数组，找到适宜的分数线。

因为本题 n\le10^5，快排和插入都会超时，观察到每个选手的成绩均不超过 600，所以考虑用桶记录每个成绩有多少人。

每次加入成绩就将成绩入桶，倒序遍历桶，记录成绩大于等于当前成绩的人数，当人数达到获奖人数时，就输出分数线。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[605],k,x;
int main(){ 
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[x]++;//成绩入桶
        int m=max(1,i*k/100),t=0;
        for(int j=600;j>=0;j--){
            t+=a[j];//累加人数
            if(t>=m){
                cout<<j<<" ";//人数达到获奖人数就输出
                break;
            }
        }
    }
    return 0;
}