CF1042A 【Benches】(优先队列)

这是一道良心的cf题

题意里让你求的是来了m个人后人数最多的长椅上最少和最多有多少人

如果要求最多，很好办，m个人都挤到原来人数最多的长椅上了（一眼看出）

但如果要求最少呢？

大家看图

长椅某个时间的人数如图

显然，如果你往最高峰上放~~（怕不是石乐志）~~，一定会增加答案

自然不是最优

那我们怎么办呢？

填坑就好了

每次找见坑，把人填进去

我们看

m $lognlog_nlogn无压力$

所以我们可以开一个优先队列（小根堆）

每次选最小的一个拿出来，加上一个人

再放回去

最后小根堆的最后一项就是答案

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define rii register int i
#define rij register int j
using namespace std;
int x[105],n,m,maxn;
priority_queue<int>q;
int main()
{
    cin>>n;
    cin>>m;
    for(rii=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        q.push(-1*x[i]);
        maxn=max(maxn,x[i]);
    }
    maxn+=m;
    for(rii=1;i<=m;i++)
    {
        int ltt=q.top();
        q.pop();
        ltt--;
        q.push(ltt);
    }
    int kkk=0;
    for(rii=1;i<=n;i++)
    {
        kkk=min(kkk,q.top());
        q.pop();
    }
    kkk*=-1;
    cout<<kkk<<" "<<maxn;
}