【问题描述】
现在有m个位置可以打 sif，有n+1个人在排队等着打 sif。现在告诉你 个人每个人需要多长的时间打 sif，问你第? +1个人什么时候才能打 sif。 （前?
个人必须按照顺序来）
【输入格式】
第一行两个整数n,m如上所述。
接下来?行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1
【样例解释】
山里有座庙，庙里住着钟神。
【数据规模与约定】
对于100%的数据，每个人所需用的时间不超过10 5 。
测试点 n m 测试点 n m
1 10 10 1 5000 500
2 20 10 2 100000 5000
3 50 10 3 100000 10000
4 1000 500 4 100000 20000
5 2000 500 5 100000 50000
思路：
priority_queue（优先队列）维护m个位置上打sif的人已经用的时间总和；
每次根据优先队列的性质来维护最小的那个位置；
等到n次维护之后输出最小值；
但是我们维护的是最小值，所以我们需要的是一个小根堆，但是我着实不愿手写堆（毕竟是个蒟蒻）；
所以我们对大根堆（优先队列）进行一丝丝的优化使他成为一个稍稍变态的小根堆；
这个优化是什么呢？
哈
就是所有的元素都乘-1；
来，上代码：
#include<queue> #include<cstdio>using namespace std;int n,m,ai[100001],cur;char ch;priority_queue<int>q;void qread(int &x) {x=0;ch=getchar();while(ch>'9'||ch<'0') ch=getchar();while(ch<='9'&&ch>='0'){x=x*10+(int)(ch-'0');ch=getchar();} }int main() {qread(n),qread(m);for(int i=1;i<=n;i++){qread(ai[i]),ai[i]*=-1;if(q.size()<m) q.push(ai[i]);else{cur=q.top();q.pop();cur+=ai[i];q.push(cur);}}cur=q.top()*(-1);printf("%d\n",cur);return 0; }
转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6037463.html