C++: Đếm số cách thành đội trinh sát

Bài toán: n binh sĩ chiều cao A[i]. Đội = 2 người, chênh lệch ≤ d. Đếm số cặp có thứ tự (ordered pairs) thỏa mãn.

Giải pháp O(n²): Duyệt mọi cặp (i,j), i < j, nếu |A[i]-A[j]| ≤ d thì +2 (vì (i,j) và (j,i) đều tính).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int d) {
    int ans = 0;
    for (int i = 1; i < (int)A.size(); i++)
        for (int j = 0; j < i; j++)
            if (abs(A[i] - A[j]) <= d) ans++;
    return ans * 2;
}

int main() {
    vector<int> A = {10, 20, 50, 60, 65};
    int d = 10;
    cout << solve(A, d) << endl; // 6
    return 0;
}

Kết quả

6

Các cặp: (10,20), (20,10), (50,60), (60,50), (60,65), (65,60).

Tối ưu O(n log n): Sort mảng, dùng two pointers / binary search đếm cặp.