题目链接:http://poj.org/problem?id=1083
题意: 走廊两边分别有200个房间,一边连续编号为1-399的奇数,另一边是2-400的偶数, 如果从房间 i 移动桌子到房间 j , 由于走廊宽度只能允许一次通过一张桌子, 那么给定一些移动方案, 求最小的移动时间(移动一次需要10分钟.).
分析: 每次移动都不应该占同样的走廊, 如果记录移动桌子时走廊的每段最多会被占多少次, 那么这个最大值就是最小移动次数.
- z[MAXN], z[i] 表示走廊段被占用的次数. 如 z[0] 表示1和2 房间之间的走廊被占的次数.
- 给定移动方案s->t之后, 那么同一段时间里, s 到 t 房间之间的走廊段都被占用, (注意s 有可能大于 t , 因为这个wa了几次).
#include <iostream> using namespace std; #define MAXN 200 int z[MAXN]; // 房间对应的过道(对它编号),记录经过它的次数. int main(){ int T; cin>>T; while(T--){ int n,s,t; cin>>n; for(int i=0;i<MAXN;++i) z[i] = 0; for(int i=0;i<n;++i){ cin>>s>>t; s = (s+1)>>1; t = (t+1)>>1; //因为输入可能s>t if(s>t){ s = s^t; t = s^t; s = s^t; } for(int j=s-1;j<t;++j) //走廊编号从0开始,而房间编号从1开始. z[j]++; } s = 0; for(int i=0;i<MAXN;++i) if(z[i]>s) s = z[i]; cout<<s*10<<endl; } return 0; }