支配值計算：兩個有序數組元素大小關係統計優化算法

問題描述

給定兩個已排序的整數數組 f[] 和 g[]，長度分別為 m, n (≤1000)。計算 f 中每個元素比 g 中多少元素大的總和（支配值）。

暴力解法與優化

暴力雙循環：O(m×n)，對每個 f[i] 遍歷 g[] 計數。雖然 n≤1000 可通過，但可優化。

雙指針優化：利用兩數組有序特性，維護 g 的指針 j，對每個 f[i] 只需從上次位置繼續前進。時間複雜度降為 O(m+n)。

代碼實現（暴力版）

#include <stdio.h>

int main() {
    int i, j, n, m, sum;
    int f[1001], g[1001];

    scanf("%d %d", &n, &m);
    sum = 0;

    for (i = 0; i < n; i++) scanf("%d", &f[i]);
    for (j = 0; j < m; j++) scanf("%d", &g[j]);

    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (f[i] > g[j]) sum++;
            else break;  // g 有序，後續更大，直接跳出
        }
    }

    printf("%d\n", sum);
    return 0;
}

優化版思路

// 雙指針 O(m+n)
j = 0;
for (i = 0; i < n; i++) {
    while (j < m && f[i] > g[j]) j++;
    sum += j;  // j 即為 g 中小於 f[i] 的元素個數
}

測試樣例

輸入：

5 5
1 3 5 7 9
2 3 4 7 8

輸出：

12

驗證：f[0]=1(0個) + f[1]=3(1個) + f[2]=5(3個) + f[3]=7(3個) + f[4]=9(5個) = 12