题解 P1296 【奶牛的耳语】

· · 题解

哈哈，小学生又来发题解了！

这题我用的是暴力枚举，时间复杂度最小为O(n^2/2),本来是会超时的，但由于这题的d不够大，所以可以卡过时间点。

枚举过程：

先将奶牛的位置从小到大排序，然后从1~n作为起点，再往后找，看在d范围内有多少头奶牛，然后ans++;最后输出ans。

PS：当超出d范围时就得退出循环，否则时间复杂度就真的变成O(n^2/2)，绝对会超时，所以当超出d范围时就得break。

献上代码：

#include<iostream>
#include<algorithm>
#include<cstdio>    //文件头
using namespace std;
int n,d,ans,a[100010]; //定义 ans用来统计有多少对相互交流的奶牛，a[]表示奶牛在直线上的位置
int main()
{  
    cin>>n>>d;    //输入奶牛总数n和奶牛交流的最高距离d
    for(int i=1; i<=n; i++)
    scanf("%d",&a[i]);    //输入n头奶牛的位置
    sort(a+1,a+1+n);      //将奶牛的位置从小到大排序
    for(int i=1; i<n; i++)   //枚举奶牛起点
        for(int j=i+1; j<=n; j++)      //往后找，看第j头奶牛是否可以和第i头奶牛交流
            if(a[j]-a[i]<=d)ans++; else break;    //当在d范围内时，ans++，否则记住退出（细节细节）
    cout<<ans;    //输出可以相互交流奶牛的对数ans
    return 0;     
}