ZOJ 1029 Moving Tables

　　题目大意：走廊两侧有两排房间，现在需要在房间之间移动桌子，走廊的宽度只能容纳一张桌子移动，安排方案使得桌子尽可能并发移动以使得移动的总时间最短。

　　开始感觉是选择不相交区间问题，就开始写，写着写着就卡壳了，憋不出来了...只好投降了，看书...

　　将房间之前的走廊作为一个统计单位，当所有的办公室都搬运完成之后，看看这段走廊到底被占用了多少次。统计所有走廊被占用次数的最大值max，这个值就是要单独安排的搬运次数，乘以10就是总的搬运时间。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int move[200];
12     int T;
13     scanf("%d", &T);
14     while (T--)
15     {
16         int n;
17         scanf("%d", &n);
18         memset(move, 0, sizeof(move));
19         for (int i = 0; i < n; i++)
20         {
21             int x, y;
22             scanf("%d%d", &x, &y);
23             if (x > y)
24             {
25                 int t = x;
26                 x = y;
27                 y = t;
28             }
29             x = (x-1) / 2;
30             y = (y-1) / 2;
31             for (int j = x; j <= y; j++)
32                 move[j]++;
33         }
34         int ans = -1;
35         for (int i = 0; i < 200; i++)
36             ans = max(ans, move[i]);
37         printf("%d
", ans*10);
38     }
39     return 0;
40 }

View Code

　　这个是从搬运后的结果进行考虑的。从如何安排方案方面应该也是可以的，代码以后再试试吧。有时候从结果考虑会使问题变得更简单！