題目要求

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);} }

總結

以上是生活随笔為你收集整理的快速排序+统计→奶牛的耳语（洛谷P1296题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。