HDU 5353 Average 環上糖果均分貪心+枚舉斷點

問題描述

n 個人圍成一圈，第 i 人有 a[i] 顆糖果。相鄰兩人之間可進行一次操作：左給右、右給左、或不操作。問能否通過操作使所有人糖果數相等，若能輸出操作序列。

關鍵觀察

設最終每人糖果數為 avg = (∑a[i]) / n。若不能整除則無解。
定義 d[i] = a[i] - avg（盈餘/缺口）。操作相當於在相鄰兩人之間傳遞糖果。

破環為鏈

環上難以直接貪心，枚舉 1 號和 2 號之間的關係（三種操作之一），將環在 1-2 之間斷開成鏈。對於每種情況，從左到右貪心處理：
若 d[i] > 0，第 i 人給 i+1 遞交 d[i] 顆；
若 d[i] < 0，第 i+1 人給 i 遞交 -d[i] 顆。
最終檢查 d[n] 是否為 0（即首尾匹配）。

三種枚舉情況

1. 1 號給 2 號 1 顆：d[1]--, d[2]++
2. 2 號給 1 號 1 顆：d[1]++, d[2]--
3. 1、2 號無操作：d 不變

只要有一種情況貪心成功，即有解。操作數 ≤ n。

代碼框架

bool check(vector& d, vector>& ops) {
    ops.clear();
    for (int i = 1; i < n; ++i) {
        if (d[i] > 0) { ops.emplace_back(i, i+1); d[i+1] += d[i]; d[i] = 0; }
        else if (d[i] < 0) { ops.emplace_back(i+1, i); d[i+1] += d[i]; d[i] = 0; }
    }
    return d[n] == 0;
}

int main() {
    // 讀入 n, a[], 計算 avg, d[]
    // 枚舉三種初始操作，調用 check()
    // 輸出任一可行解
}

複雜度

每次檢查 O(n)，共 3 次枚舉，總時間 O(n)。