文档章节

PAT 1017 Queueing At Bank

guoliang
 guoliang
发布于 2013/08/26 15:07
字数 317
阅读 87
收藏 0

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

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

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

#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;
}



© 著作权归作者所有

共有 人打赏支持
guoliang
粉丝 26
博文 131
码字总数 27457
作品 0
杭州
程序员
PAT B1017. A除以B (20)

A除以B (20) https://www.patest.cn/contests/pat-b-practise/1017 时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Yue 本题要求计算A/B,其中A是不超...

阿豪boy
2017/03/05
0
0
PAT 1017. A除以B (20)

本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。 输入格式: 输入在1行中依次给出A和B,中间以1空格分隔。 输出格式: 在1...

xnh_565175944
04/09
0
0
Python 基础练习 PAT水题(四)

#学习笔记 #用以练习python基础 # 原题链接:https://www.patest.cn/contests/pat-b-practise/1050 1050. 螺旋矩阵(25) 本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“...

chaunceyjiang
2017/04/26
0
0
版本之战渐酣 Opera 12 小荷已露尖尖角

在Chrome的挑逗之下,不仅Mozilla Firefox耐不住寂寞,就连一向沉稳的Opera也行动了起来,版本发布速度日益加快。今天,Opera 12.00的首个开发版本snapshot 1017发布。虽然不推荐普通用户使用...

红薯
2011/07/08
1K
19
Telerik_2012_Q3 (已破解)全套下载链接

1.TelerikOpenAccessORM201231012_SDK.zip (暂未提供下载) 2. TelerikOpenAccessORM201231012.zip 3. TelerikExtensionsforASPNETMVC201231018_Commercial.zip 4.Telerik.Web.UI201231016_D......

awbeci
2013/10/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis中jdbcType和javaType的对应关系 

Mybatis中jdbcType和javaType的对应关系 1 JDBC Type Java Type 2 CHAR String 3 VARCHAR String 4 LONGVARCHAR String 5 NUMERIC java.math.BigDecimal 6 DECIMAL java.math.BigDecimal 7 ......

DemonsI
25分钟前
3
0
Python中字符串和datetime

遇到的问题: 今天在写一个爬虫时,需要将今天的数据和昨天、一周前的数据做比较。所以就需要一个方法可以方便的计算出指定日期的前几天的日期。比如10月3号,则一周前的日期是9月26号。 问题...

akane_oimo
27分钟前
1
0
企业级 SpringBoot 教程 (四)SpringBoot 整合JPA

JPA全称Java Persistence API.JPA通过JDK 5.0注解或XML描述对象-关系表的映射关系,并将运行期的实体对象持久化到数据库中。 JPA 的目标之一是制定一个可以由很多供应商实现的API,并且开发...

itcloud
28分钟前
2
0
白话SpringCloud | 第六章:Hystrix监控面板及数据聚合(Turbine)

前言 前面一章,我们讲解了如何整合Hystrix。而在实际情况下,使用了Hystrix的同时,还会对其进行实时的数据监控,反馈各类指标数据。今天我们就将讲解下Hystrix Dashboard和Turbine.其中Hys...

oKong
38分钟前
2
0
Java JDK 11:现在可以使用所有新功能

删除了CORBA,Java EE和JavaFX支持,但添加了十几个主要新功能 目录 哪里可以下载JDK 11 Java 11 JDK中的新功能 从Java JDK 11中删除了什么 Java Development Kit(JDK)11现已普遍可用,可供...

GuoMengyue
40分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部