题解 P1296 【奶牛的耳语】

moongazer · 2017-10-06 13:26:11 · 题解

其实直接模拟就能过，然而我还是蒟蒻地写了二分。

每次枚举每一个数，然后二分查找第一个比a[i]+d大的数，具体看代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
using namespace std;
int a[1000005];
int main(){
    int n,m,i,ans=0,L,M,R;//这里把题目中的d改成了m
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }//输入
    sort(a+1,a+n+1);//先要排序
    for(i=1;i<n;i++){
        L=i;
        R=n;//二分初始化
        while(L<=R){
            M=(L+R)/2;
            if(a[M]>a[i]+m){
                R=M-1;
            }else{
                L=M+1;
            }
        }//二分第一个比a[i]+d还大的数的序号
        ans+=(L-i-1);//将ans加上二分出的数与当前数中隔了几个数
    }
    cout<<ans<<endl;//输出
    return 0;
}