POJ 1083：Moving Tables——走廊區間計數

題目描述

200 個房間沿走廊兩側排列（奇數號北側，偶數號南側）。搬運桌子從房間 s 到 t，佔用走廊段 [min(s,t), max(s,t)]。每段每 10 分鐘只能通過一張桌子。求完成所有搬運的最短時間。

關鍵轉化

房間號 → 走廊段編號：

• 房間 1,2 → 段 1
• 房間 3,4 → 段 2
• ... 公式：段 = (房間號+1)/2

每次搬運對應區間 [L, R] 的段編號範圍，每段計數器 +1。最大計數 × 10 即答案。

算法流程

1. 初始化 200 段計數器為 0
2. 每組搬運：計算段範圍 [L, R]，區間 +1
3. 掃描最大計數 maxCnt
4. 答案 = maxCnt * 10

C++ 實現

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        int cnt[201] = {0};
        for (int i = 0, s, t; i < N; ++i) {
            scanf("%d%d", &s, &t);
            if (s > t) swap(s, t);
            int L = (s + 1) / 2;
            int R = (t + 1) / 2;
            for (int j = L; j <= R; ++j) ++cnt[j];
        }
        int mx = *max_element(cnt+1, cnt+201);
        printf("%d\n", mx * 10);
    }
    return 0;
}

複雜度

• 時間：O(N × 200) ≤ 4×10⁴，極快
• 空間：O(200)