A35 题解

注意到 $n$ 的范围较大，显然不能 $n^2$，因此 $n^2 \log n$ 的快排做法显然无法通过此题。但是不难发现，题目中特意强调了每个选手的成绩均不超过 $600$，所以可以考虑 $\mathcal{O(n)}$ 的桶排。代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,w,d[605],x,k;
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>x;
        d[x]++;
        k=(i*w/100>1? i*w/100:1);
        for(int j=600;j>=0;j--){
            k-=d[j];
            if(k<=0){
                cout<<j<<' ';
                break;
            }
        }
    }
}

注意到本次使用了正常做法