山東理工大學ACM 1226：支配值數目 - C語言解題詳解

題目描述

已知兩個已按升序排列的整數數組 f[] 和 g[]，長度分別為 m 和 n（1 ≤ m, n ≤ 1000）。求 f[] 中每個元素比 g[] 中多少個元素大，將這些計數相加作為答案。

例如：
f = [1, 3, 5, 7, 9]
g = [2, 3, 4, 7, 8]
f[0]=1 比 g 全部小 → 0
f[1]=3 比 g[0]=2 大 → 1
f[2]=5 比 g[0..2] 大 → 3
f[3]=7 比 g[0..2] 大 → 3
f[4]=9 比 g 全部大 → 5
答案 = 0+1+3+3+5 = 12

輸入格式

第一行：m n
第二行：m 個整數（f[]）
第三行：n 個整數（g[]）

輸出格式

輸出支配值總和。

範例

輸入範例

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

輸出範例

12

解題思路

方法一：雙重循環暴力法 O(m×n)

由於 m, n ≤ 1000，最多 10⁶ 次比較，完全在時限內。直接雙層循環統計即可。

方法二：雙指針優化 O(m+n)

利用兩數組已排序的性質，維護一個指針 j 指向 g[] 中第一個不小於 f[i] 的位置。因為 f[] 遞增，j 只會單調右移，總複雜度線性。

參考代碼 (C語言 - 雙指針優化)

#include <stdio.h>

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

    long long ans = 0;
    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j < n && g[j] < f[i]) j++;
        ans += j; // g[0..j-1] 都小於 f[i]
    }
    printf("%lld\n", ans);
    return 0;
}

複雜度分析

• 時間複雜度：O(m + n)，雙指針單次掃描。
• 空間複雜度：O(m + n) 存儲兩數組。

注意事項

• 答案可能較大（最多 1000×1000 = 10⁶），建議用 long long 存儲。
• 題目保證輸入數組已按升序排列，無需再排序。
• 若使用暴力雙循環，注意變量類型防止溢出。