POJ 3104 二分答案解脫水排程問題

題目背景

有 n 件衣物，第 i 件含水量 num[i]。洗衣機每分鐘可脫水 k 滴，未放入洗衣機的衣物每分鐘自然脫水 1 滴。求使所有衣物脫乾的最短時間。

關鍵觀察：二分答案

若固定總時間 mid，判斷是否可行：

• 對於 num[i] ≤ mid 的衣物，自然脫乾即可，無需洗衣機。
• 對於 mid 的衣物，需安排洗衣機時間 x2，自然脫水時間 x1，滿足：
  • x1 + x2 ≤ mid
  • k·x2 + x1 ≥ num[i]
  解得 x2 ≥ ceil((num[i] - mid) / (k - 1))。

將所有需洗衣機時間加總 sum，若 sum ≤ mid 則可行。

算法流程

1. 左界 left = 1，右界 right = max(num[i])。
2. 特判 k == 1：洗衣機無優勢，答案即 right。
3. 二分 mid，計算 sum，調整區間，記錄最小可行 mid。

參考代碼 (C++)

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

using int64 = long long;
const int MAXN = 100010;
int64 num[MAXN];

int main() {
    int n, k;
    while (~scanf("%d", &n)) {
        int64 left = 1, right = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &num[i]);
            right = max(right, num[i]);
        }
        scanf("%d", &k);

        if (k == 1) {
            printf("%lld\n", right);
            continue;
        }

        int64 ans = right;
        while (left <= right) {
            int64 mid = (left + right) >> 1;
            int64 sum = 0;
            for (int i = 1; i <= n; ++i) {
                if (num[i] > mid) {
                    sum += (num[i] - mid + k - 2) / (k - 1); // ceil 整數寫法
                }
            }
            if (sum <= mid) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度與細節

• 時間：O(n log max(num))，n ≤ 10⁵ 極快。
• 整數除法向上取整技巧：(a + b - 1) / b，避免浮點誤差。
• 使用 64 位整型防止溢位。