题解 P1296 【奶牛的耳语】

洛绫璃 · 2019-08-18 00:33:46 · 题解

复杂度（nlongn+n），先排序a[n]，标记i=1,j=2，开始循环找到第一个与i相距大于m距离的奶牛，则与i组成一对的个数为 j-i-1 ，然后++i，（重点！！）j不用变，因为当前a[j]距离上个a[i]刚好第一次距离大于m，则新的i-（j-1）之间奶牛的距离必定小于m，直到j==n+1，内循环截止，直接ans+=(n+1-i-1)+(n+1-i-1-i)+(n+1-i-2-1)+...+(n+1-n-1),即ans+=（n-i+1）n-(n-i+1)(n+i)/2;跳出循环即可，看似n^2,实则是j在i的基础上逼近n然后跳出循环，复杂度为（n）;

#include<bits/stdc++.h>
  using namespace std;
int n, a[1000001], m, d[1000001], ans;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1, j = 2; i <= n; ++i) {
        for (; a[j] - a[i] <= m&&j<=n; ++j);
        if (j == n + 1) ans += (n - i + 1)*n - (n - i + 1)*(n + i) / 2, i = n + 1;
        else ans += j-i-1;
    }
    printf("%d", ans);
}