Moving Tables
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19521 Accepted Submission(s): 6672
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.
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
Asia 2001, Taejon (South Korea)
Recommend
We have carefully selected several similar problems for you: 2037 1051 1052 1789 1045
解题注意
最近打算跟着大神们的博客按照专题来学习，这道题是一道经典的贪心题目，这道题不是很难，但比较容易出错。。通过这道题的练习我也学习了不少。。也对贪心算法以及这道题的注意点有了更深刻的理解。首先如果处理输入的数据，第一点是输入的起点和终点并不能保证起点大小一定小于终点大小。第二点是如何处理对门的不能同时搬运，这个有两种做法，一种是分别对起点x,终点y进行运算(x+1)/2和(y+1)/2。或者进行判断扩大区间，如果区间起点是偶数，则x--,如果区间终点为奇数，则y++。
其次是进行筛选的过程。这个过程中首先要对区间进行排序，按照起点从小到大排序。其次便是一般的贪心过程。这个主要是要设置一个visit数组来记录这个区间是否被访问过。可以用双重for循环来求解。。实质上还是对整个数组遍历了一次，复杂度不高。但是在对和当前区间不重合的区间进行判断时，我一直忘了写该区间是否被访问过。。结果一直WA。。后来才发现。。
总之，这道题的筛选过程属于贪心，也有线性筛素数法的思想。还有很多小的细节值得注意。。对于初学还是很有好处的。。
参考代码
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}a[200];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int vis[200];
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int num1,num2;
scanf("%d%d",&num1,&num2);
a[i].x=min(num1,num2),a[i].y=max(num1,num2);
if(a[i].x%2==0) a[i].x--;
if(a[i].y%2==1) a[i].y++;
vis[i]=0;
}
sort(a,a+n,cmp);int ans=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i]=1;
ans++;
int shu=a[i].y;
for(int j=i+1;j<n;j++)
if(!vis[j]&&a[j].x>shu) //一定不要忘了判断这个区间是否被访问
vis[j]=1,shu=a[j].y;
}
}
printf("%d\n",ans*10);
}
}