X008 保龄球
大约 3 分钟
X008 保龄球
【算法】 二分查找
【C++】 二分查找、sort、pair
【难度】 普及−
X008 保龄球
一、题目简述
有 个位置,每个位置上有不同数量的瓶子。DL 每次发球会打倒恰好 个瓶子。已知倒下的瓶子数 ,需要判断是从哪个位置发球的(即找出瓶子数为 的位置编号)。如果找不到这样的位置,输出 0。
数据范围:,,共有 次询问。
二、解题思路
问题理解
题目本质上是一个查找问题:给出 个"瓶子数 位置"的映射关系,多次查询某个瓶子数对应的位置。
由于瓶子数和位置之间没有单调关系(输入的排列是任意的),直接二分查找不可行。我们需要先按瓶子数排序,建立有序的查找结构。
算法选择
使用 pair<int, int> 数组存储每个位置的(瓶子数,位置编号),然后按瓶子数排序。
排序后,对于每个查询 ,二分查找瓶子数等于 的元素。如果找到了,输出对应的位置编号;找不到则输出 0。
手动模拟
假设输入:,瓶子数分别为 (位置 1~5)。
构造 pair 数组:
(3,1), (1,2), (4,3), (1,4), (5,5)按瓶子数排序后:
(1,2), (1,4), (3,1), (4,3), (5,5)查询 :
- 二分查找:mid=3 时
a[3]=(3,1),first=3,找到,输出位置 1。
查询 :
- 二分查找:最终区间为空,未找到,输出 0。
查询 :
- 二分查找:mid=3 时
a[3]=(3,1),first=3 > 1,向左找... - 最终找到
a[1]=(1,2),输出位置 2。
注意
由于可能有多个位置的瓶子数相同,题目可能只需要输出任意一个(或第一个找到的)。使用标准二分找到任意一个即可。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
pair<int, int> a[N]; // {瓶子数, 位置}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].first;
a[i].second = i;
}
// 按瓶子数排序
sort(a + 1, a + n + 1);
int Q;
cin >> Q;
while (Q--) {
int m;
cin >> m;
// 二分查找瓶子数为 m 的位置
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid].first == m) {
ans = a[mid].second;
break;
} else if (a[mid].first < m) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:排序 ,每次询问二分查找 , 次询问总 。总复杂度 。
- 空间复杂度:pair 数组 。
五、易错点
- 不能直接对原数组二分:原数组不是有序的,必须先排序。
- 排序后丢失了原始位置信息:所以必须用 pair 同时记录瓶子和位置。
- 找不到时输出 0:二分查找未命中时需要输出 0。
