题解 P1296 【奶牛的耳语】

ironwheel · 2017-11-02 16:36:28 · 题解

//最开始用了一个小小的sort，结果无脑超时，
//然后写了个快排，依然无脑超时，才发现是枚举的问题，
//最后想用布尔数组优化，后来想到加一个break就行了.
//思路是输入，快排，选排思路枚举，如果一头牛无法与另一头牛交流，就停止判断当前奶牛。 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100001],n,d,ans=0;
void qsort(int l,int r){  //快排不说 
    int i,j,mid,p;
    i=l;
    j=r; 
    mid=a[(l+r)/2];                 
    do{
        while(a[i]<mid)i++;      
        while(a[j]>mid)j--;      
        if(i<=j){                               
            p=a[i];
            a[i]=a[j];
            a[j]=p;
            i++;
            j--;                           
        }
    }
    while(i<=j);                                  
    if(l<j)qsort(l,j);              
    if(i<r)qsort(i,r);
}
int main(){
    cin>>n>>d;
    for(register int i=1;i<=n;i++){
        cin>>a[i];
    }
    qsort(1,n);//快排qsort 
    for(register int i=1;i<n;i++){
        for(register int j=i+1;j<=n;j++){
            if(a[j]-a[i]<=d)ans++;else break;//枚举，优化，如不够就停止判断 
        }
    }
    cout<<ans;//输出 
}