ACM 題目解析：支配值數目（山東理工大學 1226）

題目描述

給定兩個已由小到大排序的整數陣列 f[]（長度 m）與 g[]（長度 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[0..4] 大 → 5 個
總和 = 0+1+3+3+5 = 12

解法一：暴力雙重迴圈（O(m·n)）

因 m,n≤1000，10^6 次比較在 1 秒內極易通過，最直觀易寫。

#include <stdio.h>
int main() {
    int m, n, f[1000], g[1000];
    scanf("%d %d", &m, &n);
    for (int i=0;i g[j]) ans++;
    printf("%lld\\n", ans);
    return 0;
}

解法二：雙指標優化（O(m+n)）

利用兩陣列已排序特性，維護指標 j 指向 g[] 中第一個 不小於 f[i] 的位置，則 f[i] 比 g[0..j-1] 大，計數即為 j。j 單調遞增，總共只掃描一次 g[]。

#include <stdio.h>
int main() {
    int m, n, f[1000], g[1000];
    scanf("%d %d", &m, &n);
    for (int i=0;i

複雜度比較

方法
時間複雜度
空間複雜度
備註
暴力雙重迴圈
O(m·n)
O(1)
碼短，資料小足夠
雙指標
O(m+n)
O(1)
最佳，適合大規模資料


常見陷阱

  
答案可能超過 32 位整數（最大 1000×1000=10^6，仍在 int 範圍，但建議用 long long）。
  
輸入陣列已保證排序，不可自行排序以免改變題意。
  
嚴格「大於」，等於不計入。