题目描述
Farmer John 建造了一个有 N（2≤N≤105) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1,x2,⋯ ,xN（0≤xi≤109）。
他的 C（2≤C≤N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？
输入格式
第 11 行：两个用空格隔开的数字 N 和 C。
第 2∼N+12∼N+1 行：每行一个整数，表示每个隔间的坐标。
输出格式
输出只有一行，即相邻两头牛最大的最近距离。
输入输出样例
输入 #1
5 3 1 2 8 4 9
输出 #1
3
这道题怎么可能是红题？
我认为此题为红题的原因是可以用STL。
思路
尽管样例是按顺序给的，但事实上位置未必是按顺序的，为了方便计算，首先要排序。
排完序后，对于每一头牛，只需要找到后面的所有和它的距离小于dd的，累计一下就好了。
不过，数据范围很大，一个一个找一定超时，需要优化，用到二分。
这样只需要把二分结果前面的所有牛加起来就行了。
代码
STL是个好东西。我用到了这里的两个函数：sort和upper_bound。
sort
这个函数相信大家都很熟悉，就是给数组排个序。
用法：sort(a.begin(),a.end())。这样可以给数组从小到大排个序。放在这道题里就是：
sort(a+1,a+n+1);//数组从1开始
当然这个函数不仅仅可以从小到大，可以从大到小或结构体排序，这些东西大佬们一定知道，这里就不赘述了。
upper_bound
没错，这才是这个代码的核心部分。它的作用是二分查找一个数在数组中出现的位置。
用法：upperupper_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。
在这里需要注意目前遍历的牛（即ii）和二分结果（即kk）都不算在内，所以这里结果要加k−i−1。
代码
相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——
代码长度17行（还没上面的分析长），时间48ms挺快）
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;//n的最大值
int a[MAXN];
int main() {
int n, d, ans = 0;
cin >> n >> d;
for (int i = 1; i <= n; i++) cin >> a[i];//输入
sort(a + 1, a + n + 1);//sort;
for (int i = 1; i <= n; i++) {//遍历每头奶牛
int k = upper_bound(a + i + 1, a + n + 1, a[i] + d) - a;//upper_bound函数，二分
ans += (k - i - 1);//保存，记录
}
cout << ans;//输出
return 0;//华丽结束
}
在百忙之中写一篇题解也比较辛苦，别忘了点个赞！
标签：sort,upper,进击,题解,隔间,bound,int,二分,奶牛 From： https://blog.csdn.net/geogenotfound/article/details/142578270