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