题解 P1296 【奶牛的耳语】

zhaowangji · 2019-08-13 16:59:42 · 题解

一开始拿到题目，我想既然是入门难度，那应该很简单啊

然后看到n<=10^6

然后。。。然后就没有然后了

就一直放在列表里没有做

貌似数据并没有那么大

#include<iostream>
#include<algorithm>
using namespace std;
int n,d;
int ans;
int a[1000007];
int main()
{
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    cin>>a[i];//读入不说了
    sort(a+1,a+n+1);//得先排序，这些题目样例都骗你是有序的
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)//双重循环枚举
    if(a[j]-a[i]<=d)ans++;
    else break;
        //从每一个点向后枚举，如果距离足够，就多了一对
        //如果不够，因为序列是有序的，所以后面的距离会更大，故直接退出循环（注意有等于号）
    cout<<ans<<endl;
    return 0;
}