题解 P1296 【奶牛的耳语】

· · 题解

这道题怎么可能是红题？

我认为此题为红题的原因是可以用STL。

思路

尽管样例是按顺序给的，但事实上位置未必是按顺序的，为了方便计算，首先要排序。

排完序后，对于每一头牛，只需要找到后面的所有和它的距离小于d的，累计一下就好了。

不过，数据范围很大，一个一个找一定超时，需要优化，用到二分。

这样只需要把二分结果前面的所有牛加起来就行了。

代码

STL是个好东西。我用到了这里的两个函数：sort和upper_bound。

sort

这个函数相信大家都很熟悉，就是给数组排个序。

用法：sort(a.begin(),a.end())。这样可以给数组从小到大排个序。放在这道题里就是：

sort(a+1,a+n+1);//数组从1开始

当然这个函数不仅仅可以从小到大，可以从大到小或结构体排序，这些东西大佬们一定知道，这里就不赘述了。

upper_bound

没错，这才是这个代码的核心部分。它的作用是二分查找一个数在数组中出现的位置。

用法：upper_bound(a.begin(),a.end(),num)。这样可以在数组中找到第一个大于num的数的地址，如果不存在就返回end。而由于是地址，就需要在最后减去a。

放在这道题里就是：

int k=upper_bound(a+i+1,a+n+1,a[i]+d)-a;//返回地址，要减去a的地址

有一个和此函数差不多的函数，叫做lowerbound，只是把上面的“大于”改成“大于等于”。但这道题用的是upperbound。

在这里需要注意目前遍历的牛（即i）和二分结果（即k）都不算在内，所以这里结果要加k-i-1。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

代码长度17行（还没上面的分析长），时间48ms（挺快）。

#include<cstdio>
#include<algorithm>//sort和bound都需要此库
using namespace std;
const int MAXN=1e6+10;//n的最大值
int a[MAXN];
int main(){
    int n,d,ans=0;
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);//排序
    for(int i=1;i<=n;i++){//遍历每只奶牛
        int k=upper_bound(a+i+1,a+n+1,a[i]+d)-a;//二分
        ans+=(k-i-1);//记录
    }
    printf("%d",ans);
    return 0;//华丽结束
}

在百忙之中写一篇题解也比较辛苦，别忘了点个赞！