1960 问题 D: 蓝桥杯算法提高VIP-Workshops

时间限制: 1s 内存限制: 128MB 提交: 22 解决: 2
题目描述
第一次加利福尼亚整体会议在1979年于旧金山举行。“加利福尼亚的”是一个轻微的夸大,因为23个参加者实际上都住在旧金山。几年后,在1987年,会议是真正的“加利福尼亚的”了,337个参加者从该州的各个地方来。自从那时起,参加者的数目像芯片尺寸那样增长。在1993年,会议被重新命名为“美国整体会议”(有2549个参加者),第二次重新命名(被重新命名为“世界整体会议”)是在1997年之后,当时参加者的数量增加到9973人。在对词语“银河”是否有排除银河外的生命形式的意味这一问题的一些讨论后,会议在2003年得到了它现在的名字(银河整体会议)。第二年,所有注册了的参加者仍然是地球上的,虽然一些参加者积极地汇报,说已经感觉到有地球外的生命出席。
专题讨论会的数量随着参加者的数量的增长而增长。对于即将开始的会议,组织方必须面对一些务实但是非常讨厌的时间安排的问题。对于2005年的这次会议而言,寄宿地点决定同时提供的专题讨论会不能超过1000个。然而他们必须租他们能够拿到的每个大厅或者教室。这些房间中的某一些只在一个受限制的时间段是可以用的。
在第一天的上午,公开会议在一个足球馆内举行。到了下午,参加者出席专题讨论会。然后,组织方的工作人员有一个所有专题讨论会的列表,和每个房间能够容纳的人数,并且每个具体房间可以使用的时间一定是清楚的。有了这些信息,工作人员必须将每个专题讨论会安排到一个在可容纳人数和时间上都足够的房间中。因为这个问题不一定能够解决,足球馆内提供了帐篷,供不能容纳到房间中的人使用。这些帐篷可以容纳足够多的人,但是它们有令人不愉快的热量和噪声。因此组织方的工作人员希望时间表能够最小化需要安排到帐篷中的专题讨论会的数量(即不能安排到房间中的专题讨论会的数量)。如果有多种答案能够最小化需要安排到帐篷中的专题讨论会的数量,工作人员希望最小化需要参加帐篷中的专题讨论会的参加者的数量。
输入
输入文件包含多组测试数据。每个测试数据由两部分组成:专题讨论会的列表和租到的房间的列表。
专题讨论会列表以一行(包含一个整数w(0<w<=1000),表示专题讨论会的数量)。
接下来的w行,每行2个整数,描述一个专题讨论会。第一个数p表示参加者的人数(0<p<=100)。第二个数d表示专题讨论会持续的时间(0<d<=300),以分钟计。为了你的方便,专题讨论会其他的细节被省略。所有的专题讨论会在14:00开始。
租到的房间的列表以一行(包含一个整数r(0<r<=1000),表示租到的房间的数量)。
接下来的r行,每行1个整数s和一个形如hh:mm的字符串,描述一个租到的房间。整数s表示房间可以容纳的人数(0<p<=100)。形如hh:mm的字符串表示房间必须腾空的时间,以24小时制表示,其中hh表示小时,mm表示分钟。所有的房间从14:00开始可以使用。所有的房间必须腾空的时间在14:01到23:59之间(包括14:01和23:59)。
输入文件以一个数字0结束。
输出
对于输入中的每个测试数据,必须输出一行,包括两个整数,需要安排到帐篷中的专题讨论会的数量和需要参加帐篷中的专题讨论会的参加者的数量。注意按照输出样例中的个数输出。
样例输入
1
20 60
1
30 16:00
2
20 60
50 30
1
30 14:50
0
样例输出
Trial 1: 0 0
Trial 2: 2 70
提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

比赛公告

欢送开学!

比赛结束欢迎提供题解! 

联系QQ群管理员有奖励!