解题思路

为了正确统计满足条件的下标对 (i,j) 且 i < j，我们需要：

1. 保持原始数组的下标关系
2. 对于每个元素 A[j]，统计前面有多少个元素 A[i] (i < j) 满足 A[i] - A[j] ≥ K

可以采用以下方法：

• 使用归并排序的思想，在排序过程中统计满足条件的对数
• 或者使用树状数组/线段树来维护元素信息

这里我们采用归并排序的变种，在排序过程中统计满足条件的对数：

1. 对数组进行归并排序
2. 在合并两个有序子数组时，统计满足 A[i] - A[j] ≥ K 的对数
3. 由于子数组是有序的，可以利用双指针高效统计

修正后的复杂度分析

• 时间复杂度：O(n log n)

  • 归并排序的时间复杂度为 O(n log n)
  • 在合并过程中统计满足条件的对数为 O(n)

• 空间复杂度：O(n)

  • 归并排序需要额外的 O(n) 空间

代码实现

Python

def count_k_dominant_pairs(arr, k):
    # 使用归并排序的思想统计满足条件的对数
    def merge_sort_count(l, r):
        if l >= r:
            return 0
        mid = (l + r) // 2
        count = merge_sort_count(l, mid) + merge_sort_count(mid + 1, r)
        
        # 统计满足条件的对数
        i, j = l, mid + 1
        while i <= mid and j <= r:
            if arr[i] - arr[j] >= k:
                count += mid - i + 1
                j += 1
            else:
                i += 1
        
        # 合并两个有序数组
        temp = []
        i, j = l, mid + 1
        while i <= mid and j <= r:
            if arr[i] <= arr[j]:
                temp.append(arr[i])
                i += 1
            else:
                temp.append(arr[j])
                j += 1
        temp.extend(arr[i:mid + 1])
        temp.extend(arr[j:r + 1])
        arr[l:r + 1] = temp
        
        return count
    
    return merge_sort_count(0, len(arr) - 1)

if __name__ == "__main__":
    import sys
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    k = int(sys.stdin.readline())
    print(count_k_dominant_pairs(arr, k))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        System.out.println(countKDominantPairs(arr, k));
        sc.close();
    }

    private static int countKDominantPairs(int[] arr, int k) {
        return mergeSortCount(arr, 0, arr.length - 1, k);
    }

    private static int mergeSortCount(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSortCount(arr, left, mid, k) + mergeSortCount(arr, mid + 1, right, k);
        
        // 统计满足条件的对数
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] - arr[j] >= k) {
                count += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        
        // 合并两个有序数组
        int[] temp = new int[right - left + 1];
        i = left;
        j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, left, temp.length);
        
        return count;
    }
}

C++

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

using namespace std;

int mergeSortCount(vector<int>& arr, int left, int right, int k) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    int count = mergeSortCount(arr, left, mid, k) + mergeSortCount(arr, mid + 1, right, k);
    
    // 统计满足条件的对数
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] - arr[j] >= k) {
            count += mid - i + 1;
            j++;
        } else {
            i++;
        }
    }
    
    // 合并两个有序数组
    vector<int> temp;
    i = left;
    j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
        }
    }
    while (i <= mid) {
        temp.push_back(arr[i++]);
    }
    while (j <= right) {
        temp.push_back(arr[j++]);
    }
    copy(temp.begin(), temp.end(), arr.begin() + left);
    
    return count;
}

int countKDominantPairs(vector<int>& arr, int k) {
    return mergeSortCount(arr, 0, arr.size() - 1, k);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int k;
    cin >> k;
    cout << countKDominantPairs(arr, k) << endl;
    return 0;
}

题目内容

给定一个整数数组 $A$，长度为 $n$ 。在给定一个整数 $K$ ，定义下标对 $(i,j)$(满足$i＜j$)，如果 $A[i]-A[j]≥K$，为「K-统治对」。

统计并返回数组中所有「K-统治对」的数量。

输入描述

数组长度 $n$ ；范围 $[1,100000]$

数组各元素，用空格分隔，元素取值范围 $[-100000,100000]$

整数 $K$

输出描述

输出一个整数，表示数组中所有「K-统治对」的数量。

样例1

输入

5
-3 -1 -6 2 0
2

输出

3

说明

满足 $A[i]-A[j]>=2$ 且 $i<j$ 的下标对如下：

$(0,2):-3-(-6)=3>=2$

$(1,2):-1-(-6)=5 >= 2$

$(3,4):2-0=2>= 2$

故最终计数为 $3$ 。

样例2

输入

5
2 9 4 7 1
2

输出

5

说明

满足 $A[i]-A[j]>=2$ 且 $i<j$ 的下标对如下：

$(1,2):9-4=5>=2$

$(1,3):9-7=2 >= 2$

$(1,4):9-1=8>=2$

$(2,4):4-1=3 >= 2$

$(3,4):7-1=6 >= 2$

共计 $5$ 个。