UVA 11054 Wine Trading in Gergovia：貪心與前綴和優化

UVA 11054 Wine Trading in Gergovia：貪心與前綴和優化

一條街上的居民買賣酒，相鄰運輸成本為 1。求最小總運輸成本。這是經典的貪心 + 前綴和問題。

問題建模

• a[i] > 0：第 i 人需買入 a[i] 單位酒。
• a[i] < 0：第 i 人需賣出 -a[i] 單位酒。
• 總和為 0，供需平衡。

方法一：雙指針貪心（模擬交易）

記錄所有賣家位置，買家優先從最左邊賣家買入。維護 left 指向當前可用的最左賣家，賣完則右移。

// 核心邏輯
for (i = 0; i < n; i++) {
    if (a[i] > 0) { // 買家
        for (j = left; j < k; j++) {
            if (a[b[j]] + a[i] <= 0) { // 賣家酒足夠
                sum += a[i] * abs(b[j] - i);
                a[b[j]] += a[i];
                a[i] = 0;
                if (a[b[j]] == 0) left++;
                break;
            } else { // 賣家酒不夠
                sum += -a[b[j]] * abs(b[j] - i);
                a[i] += a[b[j]];
                a[b[j]] = 0;
                left++;
            }
        }
    }
}

方法二：前綴和數學優化（O(N) 精簡版）

核心洞察：第 i 人將手中酒（正為買入，負為賣出）傳遞給 i+1，成本即為 |prefix[i]|。總成本 = Σ |prefix[i]|。

for (i = 0; i < n - 1; i++) {
    sum += abs(a[i]);
    a[i + 1] += a[i];
}

為什麼前綴和有效？

考慮酒在街道上流動：每個位置 i 的淨流量為 a[i]，流經邊 (i, i+1) 的酒量絕對值即為 |Σ_{k=0}^i a[k]|。無論具體怎麼匹配買賣雙方，酒必須流經這些邊，總成本固定。

完整代碼（前綴和版）

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define LL long long

int main() {
    int n;
    LL a[110000];
    while (scanf("%d", &n) && n) {
        LL sum = 0;
        for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
        for (int i = 0; i < n - 1; i++) {
            sum += abs(a[i]);
            a[i + 1] += a[i];
        }
        printf("%lld\n", sum);
    }
    return 0;
}

複雜度對比

此題深刻體現了「貪心即最優」與「全局最優等於局部流量和」的等價性，是貪心算法與前綴和技巧的經典結合。