X009 奶牛的拉长耳朵
大约 3 分钟
X009 奶牛的拉长耳朵
【算法】 二分查找、排序
【C++】 二分查找、upper_bound
【难度】 普及−
X009 奶牛的拉长耳朵
一、题目简述
头奶牛在一条直线上,第 头奶牛的坐标为 (可以重复)。声波传播距离为 。任意两头奶牛,如果它们之间的距离 ,就可以互相交流。求能互相交流的奶牛对数(无序对,即 和 算同一对)。
数据范围:,,。
二、解题思路
问题分析
"距离 " 意味着 ,即 。
对于一对奶牛 ,如果它们能交流,那么其中坐标较大的那个一定落在坐标较小的那个的 范围内。
算法选择
先对坐标排序。排序后,对于每头牛 (作为坐标较小的那头),我们找它右边有多少头牛的坐标 。这些牛都可以和牛 交流。
注意我们只往右边找(找 且 ),这样就避免了重复计数。
对每个 ,用 upper_bound 找到第一个 的位置 ,则能与 交流的牛是 ,贡献 对。
另一种等价写法:int r = upper_bound(p+1, p+n+1, p[i] + d) - p - 1;,则 范围的牛都能与 交流,贡献 对。
手动模拟
假设 ,坐标 ,。
排序后(已在输入时排好):。
- :找 的牛。
upper_bound返回位置 3(第一个 的是 5)。(最后一个 的是位置 2,值 3)。贡献 对:。 - :找 的牛。
upper_bound返回位置 5(第一个 的是 10)。(最后一个 的是位置 4,值 6)。贡献 对:。 - :找 的牛。
upper_bound返回位置 5。。贡献 对:。 - :找 的牛。
upper_bound返回位置 5。。贡献 对。 - :右边没有牛,贡献 0。
总对数:。
验证:距离 的奶牛对有 无 无 无 。确实 共 4 对。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long p[N];
int main() {
int n, d;
cin >> n >> d;
for (int i = 1; i <= n; i++) cin >> p[i];
// 按坐标排序
sort(p + 1, p + n + 1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
// 找到最后一个 <= p[i] + d 的位置
int r = upper_bound(p + 1, p + n + 1, p[i] + d) - p - 1;
// i+1 到 r 都可以和 i 交流
ans += r - i;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 , 次二分查找每次 。总复杂度 。
- 空间复杂度:坐标数组 。
五、知识扩展
为什么只往右找不会漏?
因为我们只统计有序对 且 (排序后的小下标和大下标)。如果牛 和牛 能交流,且 ,那么在遍历 时就会把 算进去。遍历 时不会再算 ,避免了重复。
另一种思路:双指针
由于坐标排序后是单调的,还可以用双指针(滑动窗口)来做:维护 和 ,对每个 ,移动 直到 ,则窗口 内的都能和 交流。复杂度同样是 (排序主导),但双指针部分是 的。这在 非常大时比二分更优。
