题解 P1296 【奶牛的耳语】

· · 题解

其实按这题的数据范围，难度决不止入门（我刚开始交了个暴力t了两个点）

然而由于数据的仁慈，许多时间复杂度十分接近暴力的程序通过了这题，使得这题的难度标签被拉了下来。事实上在某些阶段数据（如d很大【声音传得超~远】，奶牛之间离得很近，这时排序后的【数据有序】这一红利将大为减小，还要搭上排序的O(nlogn)时间）

--------------------正片开始--------------------

前面说过在某些极端数据下排序+暴力会使【数据有序】这一红利大大减小，那该怎么解决呢？

看到一串有序的数列，你会想到什么？

二分

（单调队列）

想到这个一切就都好办了：首先排完序，然后从第一个点开始向后做，利用二分找出声音最多能到第几个点，然后加到累加变量里就行了。 这样最坏时间复杂度是O（nlogn【快排】+nlogn【二分】）没有最好情况，并不会超时

放出程序：

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<cmath>//大部分没有用的头文件
    #define rep(a,b,c) for(int a=b;a<=c;a++)//宏定义，就是为了下面方便，大家读的时候可以脑补成for语句，有兴趣可以去搜索一下
    #define drp(a,b,c) for(int a=b;a>=c;a--)
    #define HY 1000005
    #define lo long long
    using namespace std;
    int n,m,x,y,s,a[HY],l,r,mid;
    int main(){
      cin>>n>>m;
      rep(i,1,n) scanf("%d",&a[i]);
      sort(a+1,a+n+1);//排序只需一句话 @pascal 
       rep(i,1,n-1){ //从每个点（除最后一个点）开始都做一遍
        l=i+1; r=n; //二分标配l和r，表示目前可能的范围在l与r之间
         while(l<r){
         mid=(l+r+1)/2; //取区间的中间
          if(a[mid]-a[i]<=m) l=mid; //若条件满足，说明mid及左边都可以与第i头牛说话，就把l赋成mid
          else r=mid-1; //若条件不满足，说明mid及右边都不能与第i头牛说话，把r赋成mid-1
         } //做完后l必与r相等
        s+=l-i; //i能与i+1到l的牛说话，则都累加上去
        if(a[l]-a[i]>m) s--; //如果i连第i+1头牛都不能听到，那么说明之前多加了一对，减掉
       }
    cout<<s;    //输出之
    return 0;
    }
蒟蒻求赞_(:з」∠)_