HDOJ 1050 Moving Tables：貪心區間調度

問題建模

走廊兩側各 100 個房間，編號 1…200。移動桌子從 s 到 t 佔用走廊區間 [min, max]。
每次移動 10 分鐘，同一時間走廊任一位置只能通過一張桌子。
求完成所有移動的最少時間（10 分鐘倍數）。

關鍵觀察

房間編號奇偶對應走廊同一側位置：
奇數房間在左側，偶數在右側。
移動區間實際佔用走廊段為：
L = (s 為偶？s−1 : s) ，R = (t 為奇？t+1 : t) ，取 min/max。
每條走廊段被佔用次數 = 同時進行的移動數。
答案 = max_段 佔用次數 × 10。

差分數組統計

int cnt[405] = {0};
for (each move) {
    int s, t; cin >> s >> t;
    if (s > t) swap(s, t);
    if (s % 2 == 0) --s;
    if (t % 2 == 1) ++t;
    for (int i = s; i <= t; ++i) cnt[i] += 10;
}
cout << *max_element(cnt, cnt+401) << '\n';

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector cnt(402, 0);
        for (int i = 0; i < n; ++i) {
            int s, t; cin >> s >> t;
            if (s > t) swap(s, t);
            if (s % 2 == 0) --s;
            if (t % 2 == 1) ++t;
            for (int x = s; x <= t; ++x) cnt[x] += 10;
        }
        cout << *max_element(cnt.begin(), cnt.end()) << '\n';
    }
    return 0;
}

複雜度

O(n × 走廊長度) = O(200 × 200) = 4 萬，極快。