CSP2020J-2直播获奖

截止2025寒假第二次集训，居然没有人过题，好吧，我来出一份题解。

两种方法，都很常用：

1. Hash
2. 优先堆

Hash

此题不难想到，维护一组数，长度为i*w/100，所以，但是由于数字数量特别多，共有 $10^5$个，若是暴力解决，则供需排序$10^5$次，特别暴力。

如何做？使用hash，将当前分数存入hash表中。然后再从hash表中从大到小，依次枚举个数，减去人数，当人数小于等于0的时候，就是答案。

#include<bits/stdc++.h>
using namespace std;
int n,w,a[100012],num,b[631],ans;
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]++;
		num=max(1,i*w/100);
		for(int j=600;num>0;j--){
			num-=b[j];
			if( num<=0 )
			{
				ans=j;
				break;
			}
		}
		cout<<ans<<" ";
	}
	cout<<endl;
    return 0;
}

优先堆

STL中常用的一种，主要为维护最值。可以想到，此题需要我们维护 前$i*w/100$ 的值，则开一个最小堆，长度控制在 $i*w/100$ 超出则弹出最小值，则可以保证堆内的数字都是极大的。

注意：维护一个最大堆，动态更新两个堆之间的值。

#include<bits/stdc++.h>
using namespace std;
int n,w,x;
priority_queue<int,vector<int>,greater<int>>q;
priority_queue<int>p;
int main(){
    cin>>n>>w;
    int l=1;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        l=max(1,i*w/100);
        q.push(x);
        while( q.size()>l ) p.push(q.top()),q.pop();
        while( q.size() && p.size() && p.top()>q.top() )
        {
            p.push(q.top());
            q.pop();
            q.push(p.top());
            p.pop();
        }
        cout<<q.top()<<' ';
        //if( p.size() ) cout<<p.top();
        //cout<<endl;
    }
}