题解 P1296 【奶牛的耳语】

洛谷亿亿岁 · 2019-08-16 23:52:31 · 题解

这道题有点东西233，我想纯暴力过的

这是我的纯暴力白痴代码：

#include<bits/stdc++.h>
using namespace std;
int n,d,ans=0;
int a[1000005];
int main(){
    cin>>n>>d//输入;
    for(int i=0;i<n;i++)
    cin>>a[i];//输入
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++)//将当前和他后面的所有元素比较（因为前面的已经和自己比较过，就不用再比了）
        if(abs(a[i]-a[j])<=d)//如果距离小于d
        ans++;//多一个答案
    }
    cout<<ans;
}

但是，这T了两个点（时间复杂度n方）

这时，我才想到先排序再做

这里其实有一个巧妙的剪枝

#include<bits/stdc++.h>
using namespace std;
int n,d,ans=0;
int a[1000005];
int main(){
    cin>>n>>d;
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);//先排序啦
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[j]-a[i]<=d)//如果距离小于d
            ans++;//多一个答案
            else
            break;//这里就是剪枝，由于已经排了序，下一个a[j]会比当前的a[j]大，这一个元素都不允许了，往后所有元素都不会允许
        }
        }
    cout<<ans;
}