PAT 1017 Queueing At Bank
博客专区 > guoliang 的博客 > 博客详情
PAT 1017 Queueing At Bank
guoliang 发表于4年前
PAT 1017 Queueing At Bank
  • 发表于 4年前
  • 阅读 80
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

这道题目一般可以想到以时间为中心,进行累加,然后模拟出一个排队等待队列,然后再分配空闲的窗口就可以了。

但是更好的办法是以顾客为中心,先对顾客按到达时间进行排序。然后选出最近的顾客到达时间,和最早空闲的窗口的时间。这两个时间里面最大的时间,就是下一个顾客开始处理的时间。处理时间-到达时间即等待时间。

时间可以全部转换成秒来表示。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <functional>
#include <string>
#include <queue>

using namespace std;

int N,K;

class Person
{
public:
	int time;
	int ptime;
};
Person persons[10005];
int window[105];

int comp(const Person& a, const Person& b)
{
	return a.time < b.time;
}
int main()
{
	scanf("%d %d",&N,&K);
	for(int i=0;i<N;i++)
	{
		
		int h,m,s;
		int ptime;
		scanf("%d:%d:%d %d",&h,&m,&s,&ptime);
		int time = h*60*60 + m*60 +s;
		persons[i].ptime = ptime*60;
		persons[i].time = time;
	}
	sort(persons,persons+N,comp);

	for(int i=0;i<K;i++)
		window[i] = 8*60*60;
	
	
	int sumWait = 0;
	int num=0;
	for(int i=0;i<N;i++)
	{
		if(persons[i].time > 17*60*60)
			break;
		int* pWin = min_element(window,window+K);
		int ptime = max(*pWin,persons[i].time);
		sumWait += ptime - persons[i].time;
		*pWin = ptime+persons[i].ptime;
		num++;
	}
	
	printf("%.1f",((float)sumWait/num)/60);
	return 0;
}



标签: PAT1017
共有 人打赏支持
粉丝 27
博文 115
码字总数 27457
×
guoliang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: