快速排序+统计→奶牛的耳语（洛谷P1296题题解，Java语言描述）

题目要求

P1296题目链接

分析

这红题……不太好做啊啊哈哈……

输入的奶牛位置不一定是有序的，要排个序，用内置的快排就行……

读入完调内置排序算法排一下序，max存能与第i头牛交流的坐标编号最大的牛的索引……

当i变大时，max一定不会变小（单调不减）……

所以统计的时候只跑一趟，就是O(N)……

众所周知快排O(NlogN)……

所以依据数据结构的基础知识，加起来自然是O(NlogN)，这就很棒棒啦……

（据说本题O(N²)也能过，但是太暴力就不行了呢）

AC代码（Java语言描述）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] array = new int[num+2];
        int distance = scanner.nextInt(), max = 2, result = 0;
        for(int i = 1; i <= num; i++) {
            array[i] = scanner.nextInt();
        }
        scanner.close();
        Arrays.sort(array, 1, num+1);
        for(int i = 1; i < num; i++) {
            while(max <= num && array[max]-array[i] <= distance) {
                max++;
            }
            max--;
            result += (max-i);
        }
        System.out.println(result);
    }
}