引自免费微信小程序:皆我百晓生
为了解决这个问题,我们可以采用二分查找算法来优化查找过程。由于题目要求按照科技创新奖的获奖名单顺序输出,我们首先需要对特殊贡献奖的获奖名单进行排序,然后对于每一个科技创新奖得主,我们在特殊贡献奖的获奖名单中使用二分查找来判断此人是否也获得了特殊贡献奖。
下面是实现这一思路的C++代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool binarySearch(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return true;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
vector<int> scienceTech(n);
vector<int> specialContribution(m);
// Read the list of people who won the science and technology award.
for (int i = 0; i < n; ++i) {
cin >> scienceTech[i];
}
// Read the list of people who won the special contribution award.
for (int i = 0; i < m; ++i) {
cin >> specialContribution[i];
}
// Sort the list of people who won the special contribution award.
sort(specialContribution.begin(), specialContribution.end());
// Check each person from the science and technology award list.
for (int i = 0; i < n; ++i) {
if (binarySearch(specialContribution, scienceTech[i])) {
cout << scienceTech[i] << " ";
}
}
cout << endl;
return 0;
}
这段代码首先读取了两个奖项的获奖者列表,接着对特殊贡献奖的获奖者列表进行了排序,然后遍历科技创新奖的获奖者列表,并对每一个获奖者使用二分查找算法在特殊贡献奖的获奖者列表中查找。如果找到匹配,则输出该获奖者的编号。
注意:在实际应用中,为了提高效率,可以考虑使用STL中的std::set
或std::unordered_set
等容器,它们提供了更高效的查找方法,但这里为了符合题目的要求,我们使用了基本的二分查找算法。