HDU 2578 Dating with girls (1)：排序 + 二分查找 / 雙指針

問題描述

給定 n 個整數和目標值 k，求有多少對不同的數 (x, y) 滿足 x + y = k。數對視為無序，即 (x,y) 和 (y,x) 算同一對；x 和 y 可以相等（需至少出現兩次）。輸出滿足條件的不同數對個數。多測試用例。

核心思路

去重 + 查找：

1. 讀入數組，排序。
2. unique 去重，得到不重複值數組 a[0..cnt-1]。
3. 對每個 a[i]，若 a[i] ≤ k，二分查找 k - a[i] 是否存在於 a 中。
4. 計數器累加。

或雙指針：i=0, j=cnt-1，根據 a[i]+a[j] 與 k 比較移動指針，O(cnt)。

代碼實現（二分版）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

int bin_search(int* a, int l, int r, int key) {
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] == key) return mid;
        else if (a[mid] > key) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        vector a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        int cnt = 0;
        for (int x : a) {
            if (x <= k && bin_search(a.data(), 0, a.size()-1, k - x) != -1)
                ++cnt;
        }
        cout << cnt << '\n';
    }
    return 0;
}

樣例解析

輸入：4 4 / 2 2 2 2
去重後 [2]，2+2=4，存在 → 輸出 1。正確。

複雜度

排序 O(n log n)，去重 O(n)，查找 O(cnt log cnt) 或 O(cnt)。n ≤ 100000 完全滿足。

易錯點

1. 題目要求「不同的數對」，必須去重。
2. x 和 y 可相等，但原數組需至少有兩個該值（去重後邏輯自動處理：x == k-x 時只要集合中存在即可，因為去重不影響存在性）。
3. 雙指針寫法需注意去重邏輯，二分更直觀。