题解 P1296 【奶牛的耳语】

_Andy_Lin_ · 2019-11-19 18:25:16 · 题解

与诸位大佬不一样，我用了倍增来解决此题。

第一步：快排（好像大家都一样）

第二步：对每头牛进行这样一个操作： 用变量k记录第i头牛最远能跟后面第几头牛谈话，起初k=i。然后再用一个变量p表示可以往前扩展几头牛，起初p=1。如果可以与第k+p头牛谈话，就将k加上p，将p乘上2。否则，将p除以2。直到p=0停止操作。此时，第k头牛就是最远的谈话对象。将ans加上k-i。

最后愉快的输出ans就好啦！

代码如下

#include<bits/stdc++.h>//万能头文件
using namespace std;
int n,d,a[1000001],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);//C党的优越感
    for(int i=1;i<=n;i++){//倍增算法实现
        int k=i,p=1;
        while(p){
            if(k+p<=n&&a[k+p]-a[i]<=d){
                k+=p;
                p*=2;
            }
            else p/=2;
        }
        ans+=k-i;
    }
    printf("%d",ans);
    return 0;
}