POJ 2231：Moo Volume——貪心計算距離和

題目描述

N 條牛位於數軸上，求所有牛對之間距離之和。N ≤ 10000。

貪心 / 前綴和推導

排序位置 x₁ ≤ x₂ ≤ ... ≤ xₙ。總和 = Σ_{i

對第 i 條牛（1-based），它作為右端點出現 i-1 次，左端點出現 n-i 次，貢獻 xᵢ × (2i - n - 1)。或用遞推：

sum = Σ xᵢ - n·x₁  // 以第一頭牛為基準
ans = sum
for i=2..n:
    d = xᵢ - xᵢ₋₁
    sum += d × (2i - n - 1)  // 或 sum = sum - (n-i+1)d + (i-1)d
    ans += sum

C++ 實現

#include <cstdio>
#include <algorithm>
using namespace std;
long long x[10005];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++i) scanf("%lld", &x[i]);
        sort(x, x+n);
        long long ans = 0, cur = 0;
        for (int i = 1; i < n; ++i) cur += x[i] - x[0];
        ans = cur;
        for (int i = 1; i < n; ++i) {
            long long d = x[i] - x[i-1];
            cur += d * (2LL*i - n + 1); // 推導見正文
            ans += cur;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 排序：O(n log n)
• 掃描：O(n)