学步园

Moving Tables Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 26679   Accepted: 8926 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 file. 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 3 + N -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 Taejon 2001

题目大意：

这道题是说，有４００个房间，分别在南边和北边各２００个，然后中间隔着一条走廊，你只要每次输入一个移动桌子的编号，求出移动完所有指标后的最小时间．

解题思路：

这题一读就是线段覆盖的问题，我们可以这样想，假设所有的　ｆｒｏｍ比ｔｏ小，那么这样的话，就会自动构成一个线段，而每一间房子前面都对应这一个走廊，我们只需要求出这个走廊的前面的过道被用过几次，找出那个用的次数最为多的走廊，那么次数＊１０就是我们所需要的最终的结果了，是不是很水？证明的话，其实更为简单了，也就是说只要你找到了那个使用次数最多的，那么比这个次数都少的都会被在这段时间内被移动了，不管是否同时移动还是存在时间的先后关系．

代码：

# include<cstdio>
# include<iostream>
# include<cstring>

using namespace std;

# define MAX 233

int dis[MAX];
int from;
int to;

int main(void)
{
    int t;cin>>t;
    while ( t-- )
        {
            int n;cin>>n;
            memset(dis,0,sizeof(dis));
            for ( int i = 0;i < n;i++ )
                {

                    cin>>from>>to;

                    if ( from > to )
                        {
                            int t = from;
                            from = to;
                            to = t;
                        }
                    from = (from+1)/2;
                    to = ( to+1)/2;

                    for ( int j = from;j <= to;j++ )
                            {
                                dis[j]++;
                            }


                }

                int ans = 0;

                for ( int i = 1;i <= 200;i++ )
                    {
                       if ( dis[i] >= ans )
                            ans = dis[i];
                    }

                    cout<<ans*10<<endl;

        }



    return 0;
}