将条件改写为A[i] - B[i] > - (A[j] - B[j])，问题就变成了C[i] > - C[j]的检测，排序后，通过合并数组C和求逆的数组-C（不需要显式求逆，只需要调整索引），就可以轻松地解决这个问题，除非有更快的排序。

如注解中所述，关系对应于C[i] > -C[j]，其中C[i] = A[i] - B[i]。
在对C进行排序之后，计数变得很容易。
我们只需要注意排除i == j的情况，并考虑到直接求和会使情况的数量加倍。
复杂性主要取决于排序：时间复杂度O（n）

#include <iostream>
#include <vector>
#include <algorithm>

int n_compar_bf (const std::vector<int>& A, const std::vector<int>& B) {
    int comparisons = 0;
    for (int i = 0; i < A.size(); i++) {
        for (int j = i+1; j < A.size(); j++) {
            if (A[i] + A[j] > B[i] + B[j]) {
                comparisons++;
            }
        }
    }
    return comparisons;
}

int n_compar_opt (const std::vector<int>& A, const std::vector<int>& B) {
    int n = A.size();
    std::vector<int> C (n);
    for (int i = 0; i < A.size(); i++) C[i] = A[i] - B[i];
    std::sort (C.begin(), C.end());
    int comparisons = 0;
    int right_index = n-1;
    for (int left_index = 0; left_index < n; left_index++) {
        while ((C[left_index] > -C[right_index]) && (right_index >= 0)) {
            right_index --;
        }
        comparisons += (n-1-right_index);
        if (right_index < left_index) comparisons --;  // to exclude the case i==j
    }
    comparisons /= 2;   // because pairs (i, j) have been counted twice
    return comparisons;
}

int main() {
    std::vector<int> A = {2, -4, -5, 8, 1, 13, 0, 2};
    std::vector<int> B = {5, 2, -2, -13, 0, 4, 7, 5};
    std::cout << "brute force: " << n_compar_bf (A, B) << "\n";
    std::cout << "new: " << n_compar_opt (A, B) << "\n";
    return 0;
}

我已经做了下面的实现，但是在某些情况下，它给予的值比ans少1，我不知道为什么。这段代码中包含了一个这样的输入情况。

#include <iostream>
    #include <algorithm> // for sort
    
    int count_comparisons(std::vector<int>& A, std::vector<int>& B) {
        int comparisons = 0;
    
        // define C as A[i] - B[i] for all i
        std::vector<int> C(A.size());
        for (int i = 0; i < A.size(); i++) {
            C[i] = A[i] - B[i];
        }
    
        // sort C in ascending order
        std::sort(C.begin(), C.end());
    
        for (int i = 0; i < A.size(); i++) {
            // count the number of values C[j] to the right of i where C[i] > A[i] - B[i]
            int count = A.size() - (std::upper_bound(C.begin(), C.end(), -C[i+1]) - C.begin()) - 1;
            comparisons += count;
        }
    
        return comparisons/2;
    }
    
    
    int main() {
        std::vector<int> A = {5,10,5, 7};
        std::vector<int> B = {2, 4, 6, 8};
    
        int comparisons = count_comparisons(A, B);
        std::cout << "Number of comparisons: " << comparisons << std::endl;
    
        return 0;
    }