POJ 3663 Costume Party（排序 + 雙指針/二分計數對數）

POJ 3663 Costume Party - 牛的距離配對計數

給定 n 頭牛的距離，求有多少對牛的距離和 ≤ S。n ≤ 100,000。

解法：排序 + 雙指針

1. 過濾掉距離 ≥ S 的牛（無法配對）
2. 剩餘距離排序
3. 雙指針：i 從左，j 從右
   • 若 a[i] + a[j] ≤ S：i 與 [i+1..j] 都合法，計數 += j-i，i++
   • 否則 j--

完整代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int a[MAXN];

int main() {
    int n, S;
    while (scanf("%d%d", &n, &S) == 2) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int x; scanf("%d", &x);
            if (x < S) a[cnt++] = x;
        }
        sort(a, a + cnt);
        
        long long ans = 0;
        for (int i = 0, j = cnt - 1; i < j; ) {
            if (a[i] + a[j] <= S) {
                ans += j - i;
                i++;
            } else {
                j--;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• 排序：O(n log n)
• 雙指針：O(n)
• 總時間：O(n log n)，n=100,000 完全可行

關鍵優化

• 預先過濾 x ≥ S 的元素，減少排序規模
• 用 long long 存儲答案（最大約 5e9）
• 雙指針比二分查找更快（O(n) vs O(n log n)）