PAT甲级 1014 Waiting in Line (30 分)
程序员文章站
2024-03-17 23:45:34
...
题意:n个窗口,每个窗口可以排m人。有k为顾客需要办理业务,给出了每个客户的办理业务时间。
银行在8点开始服务,如果窗口都排满了,客户就得在黄线外等候。如果有一个窗口用户服务结束,
黄线外的客户就进来一个。如果有多个可选,选窗口id最小的。
输出查询客户的服务结束时间。
如果客户在17点或者以后还没开始服务,就输出Sorry
如果已经开始了,无论多长都会继续服务的。
思路:
建立一个优先队列,存储在黄线之内的所有客户。
对于m*n之前的人,依此往窗口里排队(即优先级队列里)即可。
对于之后的人,从优先级队列里取出结束时间最少的客户,有相同的话则是窗口最小的,进入他所在的队列。
同时还要建立window数组,存储每个窗口排在末尾客户的结束时间。
每进来一个人更新一次window数组,同时记录开始和结束时间。
最后对于需要查询的客户,如果起始时间>=17:00,则输出Sorry
否则输出对应的结束时间即可,这里方便起见,以分数存储的,所以最后还要转化一下。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define pb push_back
typedef pair<int,int> pa;
int n,m,k,q;
const int N = 1005;
struct node
{
int t,st=0,ed=0,id;
}a[N*10];
int window[N];
void init()
{
priority_queue<pa,vector<pa>,greater<pa> > q;
int xx=0;
for(int i=1;i<=m&&xx<k;i++)
for(int j=1;j<=n&&xx<k;j++)
{
a[++xx].st=window[j];
a[xx].ed=window[j]=a[xx].st+a[xx].t;
a[xx].id=j;
q.push({a[xx].ed,j});
}
for(int i=xx+1;i<=k;i++)
{
pa tem=q.top();q.pop();
int id=tem.second;
a[i].st=window[id];
window[id]=a[i].ed=a[i].st+a[i].t;
q.push({a[i].ed,id});
}
}
void f(int t)
{
int h=t/60+8,min=t%60;
printf("%02d:%02d\n",h,min);
}
int main()
{
int maxt=60*9;
cin>>n>>m>>k>>q;
for(int i=1;i<=k;i++)
cin>>a[i].t;
init();
while(q--)
{
int x;
cin>>x;
if(a[x].st>=maxt)
cout<<"Sorry"<<endl;
else
f(a[x].ed);
}
return 0;
}
参考博客:https://www.cnblogs.com/chenxiwenruo/p/6740687.html
推荐阅读
-
PAT 甲级1014 Waiting in Line (30 分)
-
PAT甲级1014 Waiting in Line (30)(30 分)
-
PAT甲级 -- 1014 Waiting in Line (30 分)
-
PAT甲级 1014 Waiting in Line (30 分)
-
PAT甲级1014 Waiting in Line (30 分)
-
PAT甲级 - 1014 Waiting in Line (30 分)
-
PAT 甲级 1014 Waiting in Line (30 分)
-
PAT甲级 1014 Waiting in Line (30 分)
-
PAT甲级 1022 Digital Library (30分)
-
PAT甲级 -- 1131 Subway Map (30 分)