HDU 2850 Load Balancing：貪心策略最小化服務器負載差

題目重述

M 台服務器，N 個任務（耗時 Ti），將每個任務分配給一台服務器，使 max(負載) - min(負載) 最小。輸出每個任務分配的服務器編號（0-based）。N≤1e5, M≤100。

貪心證明與策略

經典「多路處理機調度」近似最優解：任務按耗時降序，每次分配給當前負載最小的服務器。
直觀理解：大任務優先安排，避免最後大任務被迫疊加導致極大差值。此為 LPT（Longest Processing Time first）演算法，保證 4/3 - 1/(3m) 近似比。

實現細節

1. 讀入任務保存 (time, 原始索引)，按 time 降序排序。
2. 維護 load[M] 記錄各服務器當前總耗時。
3. 遍歷排序後任務，線性掃描 M≤100 找 load 最小者，分配並更新。
4. 按原始索引序輸出分配結果。

核心代碼

#include <cstdio>
#include <algorithm>
using namespace std;
struct Task { int time, idx, ans; } t[100001];
int load[101];

bool cmp(Task a, Task b) { return a.time > b.time; }
bool cmpIdx(Task a, Task b) { return a.idx < b.idx; }

int main() {
    int T, n, m; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &t[i].time);
            t[i].idx = i;
        }
        sort(t, t+n, cmp);
        fill(load, load+m, 0);
        for (int i = 0; i < n; i++) {
            int mi = 0;
            for (int j = 1; j < m; j++)
                if (load[j] < load[mi]) mi = j;
            t[i].ans = mi;
            load[mi] += t[i].time;
        }
        sort(t, t+n, cmpIdx);
        printf("%d\n", n);
        for (int i = 0; i < n; i++) {
            if (i) putchar(' ');
            printf("%d", t[i].ans);
        }
        puts("");
    }
    return 0;
}

複雜度

排序 O(N log N)，分配 O(N*M)（M≤100 可接受），總體 O(N log N)。空間 O(N)。