题解 P1296 【奶牛的耳语】

· · 题解 



# ------------保证最优------------

必须用快排！不排序的话，即使时间过了内存也会爆！在筛选阶段也可以利用
二分法和题意的逻辑进行优化！但此题二分的效果不明显。

------------

#include<bits/stdc++.h>//万能头文件
#include<algorithm>//算法库
using namespace std; 
int main()
{
    int n,d,i;//n为牛总数，d为传播范围
    cin>>n>>d;
    int p[n];//定义大小为n的数组p，记录各牛位置
    for(i=0;i<n;i++)
    cin>>p[i];
    sort(p,p+n);//c++快排函数
    int s=0,c,len=p[n-1]-d,mid=1,l,h;
    //s为答案，c为当前牛可听到的最右边(避免重复计算，所以用变量了)
    len为需要遍历的最右边（因为在最后的d范围内的牛肯定能互相交流）
    mid、l、h均为二分参数
    for(i=0;p[i]<len;i++)//从左向右遍历，求出每头牛向右可相互交流
    的组数
    {
        c=p[i]+d;//当前c
        l=mid,h=n-1;//二分法求出在c右边的第一头牛（不能交流的
    第一头牛）位置mid。此处有一小技巧：因为牛是非降序排列，当p[i]右移时
    上一次的mid肯定是当前mid的下限，所以每次计算的l都能用上次mid
        mid=(l+h)/2;
        while(l<h)//二分找牛
        {
            if(p[mid]<=c)l=mid+1;
            else h=mid;
            if(p[mid]>c&&p[mid-1]<=c)break;
            mid=(l+h)/2;
        }//也可用for(int j=mid;p[j]<=c;j++);mid=j;暴力找牛
        s+=mid-i-1;
        //两头牛位置相减再减1即为该次循环可交流组数
    }s+=(n-i)*(n-i-1)/2;//加上最后d范围（排列组合）
    cout<<s;
    return 0;
}

------------
顶一下

**