luogu-P7072-直播获奖

题目连接

• 该题是CSP-J2-2020-T2

---

题目大意

输入 n n n 个数，要求实时输出前若干名的分数线所在值。

---

题目分析

1、看起来是多次排序题， n n n 是 1 0 5 10^5 105 ，感觉会超时；
2、因为选手的分数值域是 1 − 600 1-600 1−600 的整数，所以显然是用桶；
3、时间复杂度为 O ( n ∗ 600 ) O(n*600) O(n∗600) 。

---

参考代码

//T2-直播获奖 
//CSP-J2-2020
//桶基础 
#include<bits/stdc++.h>
using namespace std;
int n, w, x, t[607];
signed main(){
    scanf("%d%d",&n,&w);
    for(int i = 1; i <= n; ++i){
        scanf("%d",&x);
        t[x]++;
        int rk = max(1, i*w/100), sum = 0;
        for(int j = 600; j >= 0; --j){
            sum += t[j];
            if(sum >= rk){
                printf("%d ", j);
                break;
            }
        }
    }
    return 0;
}