Moving Tables
分析
- 設使用次數最多的那一段走廊的使用次數k,那麼少于k個時段是不可行的。但是否需要多于k個時段呢?
- 通過貪心政策可以得到一個不超過的k的任務排程方案,是以可以确定隻需k個時段即可完成搬運任務;
- 任務排程政策:按任務的走廊起點編号将所有任務按升序排列(從左向右),即先安排起點小的搬運任務(假設已經調整了起點、終點的大小關系);
- 對于任意一個任務,一定可以被安排(起點一定有空位,其右側一定是空閑的)
代碼
#include <bits/stdc++.h>
using namespace std;
#define MXN 210
// r[]房号對應的走廊編号,c[]計數
int n, r[MXN<<1], c[MXN];
int main(){
int T, n, s, t;
scanf("%d", &T);
for(int i = 1; i <= 200; i++) // 房号與走廊編号的對應
r[i<<1] = i, r[(i<<1)-1] = i;
while(T--){
memset(c, 0, sizeof c);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d", &s, &t);
s = r[s], t = r[t]; // 房号轉換為走廊編号
int tmp;
if(s > t) tmp = t, t = s, s = tmp; // 編号大小調整
for(int i = s; i <= t; i++) c[i]++;
}
for(int i = 1; i <= 200; i++) c[0] = max(c[0], c[i]);
printf("%d\n", c[0]*10);
}
return 0;
}