首页 > 代码库 > 清北第一套题（zhx）
清北第一套题（zhx）
死亡
【问题描述】
现在有个位置可以打sif，有个人在排队等着打sif。现在告诉你前个人每个人需要多长的时间打sif，问你第个人什么时候才能打sif。（前个人必须按照顺序来）
【输入格式】
第一行两个整数如上所述。
接下来行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1
【样例解释】
山里有座庙。
【数据规模与约定】
对于的100%数据，每个人所需用的时间不超过10^5。
测试点 | 测试点 | ||||
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 |
题解：用一个优先队列轻松解决。由于优先队列由大到小排列，因此可以将时间的相反数压入队列，每次取栈顶元素。
#include<cstdio>#include<iostream>#include<queue>#include<algorithm>#include<cstring>#define N 100100using namespace std;int n,m;int t[N];long long ans;priority_queue<long long> q;int main(){ freopen("death.in","r",stdin); freopen("death.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&t[i]); for (int i=1;i<=m;i++) q.push(0); for (int i=1;i<=n;i++) { long long k=q.top(); q.pop(); k=-k; k+=t[i]; k=-k; q.push(k);//取相反数压入栈中 } ans=-q.top(); cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0;}
清北第一套题（zhx）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。