题解 P1296 【奶牛的耳语】

· · 题解

这题数据太水，让很多O(n^2)暴力卡过了，本来难度不止入门

读入完排序，$it$存能与第$i$头牛交流的坐标最大的牛的编号 当$i$变大时，$it$一定不会变小 所以统计答案$O(n)

加上快排O(nlogn)

#include<cstdio>
#include<algorithm>
using namespace std;
int n,d,a[100001],it=2,ans;
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<n;++i){
        while(it<=n&&a[it]-a[i]<=d)++it;
        --it;
        ans+=it-i;
    }
    printf("%d",ans);
}