SDUT 2886 Weighted Median：線性時間加權中位數求解

SDUT 2886 Weighted Median：線性時間加權中位數求解

題目大意

給定 n (≤10⁷) 個元素 x_i 及權重 w_i。加權中位數 x_k 滿足：
∑_xik w_i < S/2 且 ∑_xi>xk w_i ≤ S/2，其中 S = ∑w_i。
多測試案例，輸出中位數對應的 x 值。S 可能超 32 位。

解法

1. 讀入所有 (x, w)，計算總權重 S（用 64 位）
2. 按 x 排序
3. 掃描維護前綴權重 pref，對於位置 i，左側權重 = pref - w[i]，右側權重 = S - pref
4. 找到第一個滿足 左側 < S/2 且 右側 ≤ S/2 的元素

AC 代碼

#include 
#include 
using namespace std;

const int MAXN = 10000000 + 5;
struct Node { int x, w; } a[MAXN];

bool cmp(Node a, Node b) { return a.x < b.x; }

int main() {
    int n;
    while (~scanf("%d", &n)) {
        long long S = 0;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i].x);
        for (int i = 0; i < n; ++i) { scanf("%d", &a[i].w); S += a[i].w; }
        sort(a, a + n, cmp);
        long double half = S * 0.5L;
        long long pref = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            long long left = pref;
            long long right = S - pref - a[i].w;
            if (left < half && right <= half) { ans = a[i].x; break; }
            pref += a[i].w;
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 排序 O(n log n) 是瓶頸，n=10⁷ 需快速 I/O 與優化排序
• 掃描邏輯：left 為嚴格小於 x_k 的權重和，right 為嚴格大於的權重和
• 用 long double 存 half 避免精度問題
• 題目保證解唯一

樣例

輸入：
7
10 35 5 10 15 5 20
10 35 5 10 15 5 20

輸出：
20

此題考察加權中位數定義理解與線性掃描實現，排序後單趟遍歷即可。