洗澡
时限1s
bath.pascal/c/cpp
【题目描述】
在某大学，洗澡是非常困难的事情。澡堂有m个房间，每个房间只能同时由一个人洗。当某个人来洗澡时，如果有空闲的房间，他就会随机选择一个去洗，否则会加入等待的队列，直到有新的空闲房间。现在有n个人先于你之前去洗澡，且已知每个人洗澡时持续的时间，求你何时能够开始洗澡。
【输入】
输入的第一行是n和m，分别表示在你之前去洗澡的人数和澡堂的房间数。
接下来的n行，每行有一个数，分别表示第i个人洗澡持续的时间ti。
【输出】
输出你何时能够洗澡，如果等待时间大于600输出-1。
【输入样例】
2 3
19
30
【输出样例】
4
【数据范围】
对于30%的数据，1<=n<=1000,1<=m<=1000
对于所有数据，1<=n<=100000,1<=m<=100000
这一题可以从分利用时间只有600这个信息，利用动态规划的递推来解决，时间复杂度O(600*N)
我使用的优先队列做的
在优先队列中维护结束时间（不是持续时间），每次把最小的 Q_top 弹出（洗完了），然后加入后一个人 x ，不过这个 x 要加上弹出 Q_top ，因为我们是维护的结束时间，而弹出 Q_top 就表示当前已经是 Q_top 这个时间了，而下一个要持续 x ，所以他会在 Q_top+x 时间结束
N个人加完后，输出队首的时间即可
C++ Code
/*
C++ Code
http://blog.csdn.net/jiangzh7
By Jiangzh
*/
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=100000+10;
int n,m;
int a[MAXN];
priority_queue<int,vector<int>,greater<int> > Q;
int t=0;
void read()
{
freopen("bath.in","r",stdin);
freopen("bath.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}
void work()
{
if(n<m) {printf("0\n");return;}
int i=0;
while(i<=n)
{
if(!Q.empty()&&Q.top()>600) {printf("-1");return;}
while(Q.size()<m) Q.push(a[++i]+t);
t=Q.top();Q.pop();
while(!Q.empty()&&Q.top()==t) Q.pop();
}
printf("%d\n",t);
}
int main()
{
read();
work();
return 0;
}
