X017 统计
大约 3 分钟
X017 统计
【算法】 二分查找、排序
【C++】 二分查找、binary_search
【难度】 普及−
X017 统计
一、题目简述
科技创新奖有 名获奖者,特殊贡献奖有 名获奖者。请找出同时获得两个奖项的人,并按照科技创新奖名单的顺序输出他们的编号。
数据范围:,人员编号 。
二、解题思路
问题分析
这是一个典型的交集查找问题。我们需要找出两个列表中共同出现的人。
输出顺序有明确要求:按科技创新奖名单的顺序输出。这意味着我们不能简单地找到交集后排序(那样会打乱顺序),而是需要保持科技创新奖名单的原有顺序。
算法选择
- 对特殊贡献奖名单 进行排序(以便二分查找)
- 遍历科技创新奖名单 ,对每个 ,判断它是否在特殊贡献奖名单中出现
- 如果在,就输出
这个过程保持了科技创新奖名单的原始顺序,同时通过二分查找提高了查找效率。
STL 方案
使用 binary_search(b+1, b+m+1, a[i]),返回 bool 值,直接表示 是否在排序后的 数组中出现。
手动模拟
假设科技创新奖:
特殊贡献奖:
- 对特殊贡献奖排序:
- 遍历科技创新奖:
- :在 中二分查找,不存在,跳过
- :不存在,跳过
- :存在,输出 8
- :存在,输出 3
- :不存在,跳过
输出:8 3(保持了科技创新奖名单中的顺序)。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
// 对特殊贡献奖名单排序
sort(b + 1, b + m + 1);
// 按科技创新奖的顺序遍历,查找交集
for (int i = 1; i <= n; i++) {
if (binary_search(b + 1, b + m + 1, a[i])) {
cout << a[i] << " ";
}
}
cout << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 , 次二分查找 。总复杂度 。
- 空间复杂度:两个静态数组 。
五、知识扩展
binary_search vs lower_bound
binary_search(begin, end, val):返回bool,只判断是否存在lower_bound(begin, end, val):返回第一个 的迭代器,需额外判断是否等于 val
本题只需要判断是否存在,用 binary_search 语义更清晰。但如果需要知道具体位置,就用 lower_bound。
保持输出顺序
题目要求按科技创新奖顺序输出,这很关键。如果不在意顺序,也可以求出交集后排序,但那样会破坏原始顺序。正确的做法就是遍历科技创新奖名单,边判断边输出。
