P7072题解
Ink_Bottle
·
·
题解
阅读前，你需要注意：
- 这是一篇非常规的题解！
- 这是一篇没有用桶做的题解！
如果想要学习桶，请不要看这篇题解。
比赛的时候，我一看，这不是一道 STL 板子题吗！
上了 set，发现写不出来；
上了 multiset，发现写不出来；
上了 vector，发现还是写不出来；
………………
于是就有了这篇奇怪的题解。
主要思路
使用两个优先队列（即 priority\_queue），一个大根堆，一个小根堆。对于每个 i ，小根堆维护能够获奖的分数，大根堆维护不能获奖的分数，两堆须保证大根堆的最大值 \leq 小根堆的最小值。如不符合，则调整两堆的堆顶即可。
举个栗子：
6 60
100 200 500 300 0 200
$i=2$ 时，获奖人数为 $1$ ，大根堆插入 $200$ ，此时不满足大根堆的最大值 $\leq$ 小根堆的最小值，故交换两队堆顶，小根堆里有 ${200}$ ，大根堆里有 ${100}$ 。
$i=3$ 时，获奖人数为 $1$ ，大根堆插入 $500$ ，此时不满足大根堆的最大值 $\leq$ 小根堆的最小值，故交换两队堆顶，小根堆里有 ${500}$ ，大根堆里有 ${200,100}$ 。
$i=4$ 时，获奖人数为 $2$ ，大根堆插入 $300$ ，将小根堆空间调整为 $2$，即将大根堆堆顶插入小根堆，此时小根堆里有 ${500,300}$ ，大根堆里有 ${200,100}$ 。
$i=5$ 时，获奖人数为 $3$ ，大根堆插入 $0$ ，将小根堆空间调整为 $3$，即将大根堆堆顶插入小根堆，此时小根堆里有 ${500,300,200}$ ，大根堆里有 ${100,0}$ 。
$i=6$ 时，获奖人数为 $3$ ，大根堆插入 $200$ ，无需调整，此时小根堆里有 ${500,300,200}$ ，大根堆里有 ${100,100,0}$ 。
上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll k,f=1;
char c;
while((c=getchar())<'0'||c>'9') if(c=='-') f=-1;
k=c^48;
while((c=getchar())>='0'&&c<='9')
k=(k<<3)+(k<<1)+(c^48);
return k*f;
}
void put(ll k)
{
if(k<0) putchar('-'),k=~k+1;
if(k>9) put(k/10);
putchar(k%10+'0');
}
ll n,w,now,las,sco[1000010];
priority_queue<ll,vector<ll>,greater<ll> > q1;
priority_queue<ll,vector<ll>,less<ll> > q2;
int main()
{
//freopen("live.in","r",stdin);
//freopen("live.out","w",stdout);
n=read(),w=read();
for(ll i=1;i<=n;i++)
{
sco[i]=read();
q2.push(sco[i]);
if(q1.size()&&q2.size())
while(q1.top()<q2.top())
q2.push(q1.top()),q1.pop(),q1.push(q2.top()),q2.pop();
now=max(1ll,i*w/100);
while(q1.size()>now) q2.push(q1.top()),q1.pop();
while(q1.size()<now) q1.push(q2.top()),q2.pop();
put(q1.top()),putchar(' ');
}
return 0;
}
```