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

· · 题解

原题。

解法

考虑桶排序思想。

定义选手成绩为 a_i，和一个桶 t。

每输入一个 a_i，将 a_i 添加入桶，即 t_{a_i}\gets t_{a_i}+1。

既然分数高的获奖，则从 a_i 上限 600 遍历到下限 0，计数器计算当前人数，即 \displaystyle \sum_{i'=i}^{600} t_{i'}（i 为循环变量），随后判断人数是否大于等于 \left \lfloor i\times w\% \right \rfloor ，大于等于则当前的 i 就是获奖分数线，输出即可。

代码

复杂度：O(An)，其中 A 是 a 值域，即 600。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+1;
int a[maxn],tong[maxn];
int n,w;
int ans=0;
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tong[a[i]]++;
        int sum=0;
        for(int j=600;j>=0;j--){
            sum+=tong[j];
            if(sum>=max(1,i*w/100)){
                ans=j;
                cout<<j<<" ";
                break;
            }
        }
    }
    return 0;
}