c++ 二分查找算法+洛谷站外题

Question

站外题！
问题 A: 眼红的小王

时间限制: 1 Sec 内存限制: 128 MB
提交: 851 解决: 536
题目描述
虽然小王到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，小王就会越眼红。于是他决定统计有哪些人获得了两个奖项，来知道自己有多眼红。
输入
输入第一行，有两个数n,m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。
第二行，n个正整数，表示获得科技创新奖的人的编号
第三行，m个正整数，表示获得特殊贡献奖的人的编号

输出
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。
样例输入
4 3
2 15 6 8
8 9 2
##样例输出

2 8
提示
n<=1000，m<=1000

输入数据保证第二行任意两个数不同，第三行任意两个数不同。
@康小数 @薇同学 @一只喜欢玩MC蒟蒻 @天下第一行书 @ideal。 @智慧浩海 @一起学编程 @物随心转 @YLCHUP @皓晗
我关注的巨佬们有没有会的，一直90分RE一个

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用二分查找算法来优化查找过程。由于题目要求按照科技创新奖的获奖名单顺序输出，我们首先需要对特殊贡献奖的获奖名单进行排序，然后对于每一个科技创新奖得主，我们在特殊贡献奖的获奖名单中使用二分查找来判断此人是否也获得了特殊贡献奖。

下面是实现这一思路的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等容器，它们提供了更高效的查找方法，但这里为了符合题目的要求，我们使用了基本的二分查找算法。