本文主要是介绍Problem on Group Trip UVALive - 7219 (模拟+优先队列处理),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
点击打开链接
题目大意:有三个浴池s1,s2,s3,有n个人。每个人在每个浴池中所呆的时间为s[i].m1,s[i].m2,s[i].m3. 每次进浴池的时候要按n个人的序号的大小进行排队。
3
10 25 15
0 0 25
0 15 10
例如上面这组数据,有三个人,第一个人在s1中的时间是10,在s2中的时间是25,在s3中的时间是15,
0表示这个人不需要再该浴池中,而且每个人进入浴池的顺序是先进s1,再进s2,最后进s3,如果在si中的时间是0的话可以跳过该浴池进入下一个浴池排队等候,(注意每次排队是根据序号大小,而不是先来后到的顺序);
题解:根据要求进行模拟即可,有优先队列进行存储排队的人会容易处理点,在判断第i个浴池中有没有人或还来不来人的时候要看当前队列中是否为空和前面浴池队列中是否为空。
#include<bits/stdc++.h>using namespace std;
struct node
{int m1,m2,m3;
} s[111];
priority_queue<int ,vector<int >,greater<int> >q[10];
int main()
{int t;int w=1;scanf("%d",&t);while(t--){for(int i=0; i<=5; i++)while(!q[i].empty())q[i].pop();int n;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%d%d",&s[i].m1,&s[i].m2,&s[i].m3);if(s[i].m1!=0){q[1].push(i);}else if(s[i].m2!=0){q[2].push(i);}else if(s[i].m3!=0){q[3].push(i);}}long long sum=0;int x=0,y=0,z=0;if(!q[1].empty()){x=q[1].top();q[1].pop();}if(!q[2].empty()){y=q[2].top();q[2].pop();}if(!q[3].empty()){z=q[3].top();q[3].pop();}//cout<<x<<" "<<y<<" "<<z<<endl;int xx,yy,zz;xx=yy=zz=0;while(1){if(xx&&yy&&zz)break;sum++;if(!xx){if(x!=0){if(s[x].m1!=0)s[x].m1--;else{if(s[x].m2!=0)q[2].push(x);else if(s[x].m3!=0)q[3].push(x);if(!q[1].empty()){x=q[1].top();q[1].pop();s[x].m1--;}else xx=1;}}else xx=1;}if(!yy){if(y!=0){if(s[y].m2!=0)s[y].m2--;else{if(s[y].m3!=0)q[3].push(y);if(!q[2].empty()){y=q[2].top();q[2].pop();s[y].m2--;}else{if(xx==1)yy=1;else y=0;}}}else{if(q[2].empty()&&xx==1)yy=1;else if(!q[2].empty()){y=q[2].top();q[2].pop();s[y].m2--;}}}if(!zz){if(z!=0){if(s[z].m3!=0)s[z].m3--;else{if(!q[3].empty()){z=q[3].top();q[3].pop();s[z].m3--;}else{if(xx==1&&yy==1)zz=1;else z=0;}}}else{if(q[3].empty()&&xx&&yy)zz=1;else if(!q[3].empty()){z=q[3].top();q[3].pop();s[z].m3--;}}}}printf("Case #%d: %lld\n",w++,sum-1);}return 0;
}
这篇关于Problem on Group Trip UVALive - 7219 (模拟+优先队列处理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!