Moving Tables
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18924 Accepted Submission(s): 6460
Problem Description
The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.
The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.
For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.
The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.
For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above.
Output
The output should contain the minimum time in minutes to complete the moving, one per line.
Sample Input
3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50
Sample Output
10 20 30
Source
Recommend
心情:
博主真心要哭了,当我AC出这道题目的时候,满脸都是泪啊。快一天了,一直WA,WA,WA。。我真的像砸了笔记本,不过终于AC了,心情好了点,以后再碰到这样的题目,我不知道有没有勇气是AC。!!Orz!
错误思路:
用的是按照s升序排序,然后遍历每个区间,对于每个区间,与该区间重叠的所有区间总数记为sum[i],然后最大重叠数即为sum[]中的最大值。
错误分析:
比如说在某个大区间(1,200)内,里面有很多不重叠的小区间(1,30)(50,100)(120,150)如果按照上述方法,那么将会得到40分钟的答案,实际上大区间完成后,小区间是可以各自独立进行的,所以时间应该是20.
正确思路:
将排序方式改为以t升序排序,其他与原来思路保持一致
正确分析:
如果按照t升序将不会出现以上的小区间不重叠现象,只要与大区间重叠,小区间内必然相应的重叠
//贪心 HDU 1050 #include<cstdio> #include<algorithm> #define MAXN 210 using namespace std; int T,n,rs,rt,ans,minute; struct Room{ int s; int t; bool operator <(const Room &rhs) const{ return this->t<rhs.t; } }; void swap(int &a,int &b){ int temp = a; a = b; b =temp; } Room r[MAXN]; int main() { scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&rs,&rt); rs = (rs+1)/2; rt = (rt+1)/2; if(rs>rt)swap(rs,rt); r[i].s = rs; r[i].t = rt; } sort(r,r+n); ans = 0; for(int i=0;i<n;i++){ minute = 10; for(int j=i+1;j<n;j++){ if(r[i].t>=r[j].s){ minute +=10; } } if(minute>ans){ ans = minute; } } printf("%d\n",ans); } return 0; } //测试数据 1 19 75 154 125 158 176 48 196 65 21 171 15 170 17 100 61 116 3 189 98 104 112 19 163 66 42 14 81 168 53 165 36 143 84 140 105 199 195 151 还有更加厉害的思路,就是统计每个房间被重叠的次数,最大时间就是最大房间重叠数。
#include <iostream> #include <string.h> using namespace std; int main(){ int t; int cover[200]; cin >> t; while( t-- ){ memset(cover, 0,sizeof(cover)); int n, s, f; cin >> n; while( n-- ){ cin >> s >> f; s = (s - 1) / 2; //相邻的奇数和偶数化成同一坐标 f = (f - 1) / 2; if( s > f ) s ^= f ^= s ^= f; for(int i = s; i <= f; ++i) cover[i]++; } int max = -1; for(int i = 0; i < 200; ++i){ if( cover[i] > max ) max = cover[i]; } cout << max * 10 << endl; } return 0; }
相关推荐
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
1050 贪心;1052 贪心;1053 贪心,关于 Huffman 编码 等等。 数学题 数学题是 ACM HDU 题目分类中的一大类,例如,1006 感觉有点 BT 的题;1007 经典问题,最近点对问题,用分治;1017 简单数学题;1018 简单数学...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
hdu 1574 passed sorce
hdu2101AC代码
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
hdu 1166线段树代码
HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...