^/~c++试题~/^

Question

题目描述
安东诺夫再一次打开了《战舰世界》。

这次他打算去玩玩剧情模式，并且选择了那莱。

他开出了魏玛，打算去上路单杀 AI 的航母列克星敦。

然而在单杀航母的路上，他可能会遇到两大劫难的其中一个：

1. 被 AI 的战列舰怀俄明号一轮秒杀。

2. 遇到 AI 的战列舰密苏里，号称 小麻烦。被小麻烦一轮秒杀。

如果他躲过了这两大劫难，就能带着队友赢得剧情。

输入
第一行两个整数 n,m(1≤n,m≤10^5 )。 n 表示他有 n 局那莱剧情躲过了第一个劫难， m 表示他有 m 局那莱剧情躲过了第二个劫难。

第二行有 n 个一定不重复的整数，表示躲过了第一个劫难的对局编号。

第三行有 m 个一定不重复的整数，表示躲过了第二个劫难的对局编号。

对局编号不大于 10^9 。

输出
安东诺夫最后获得胜利的对局，按照在输入格式第二行中输入的顺序输出。
样例输入 复制
4 3
2 15 6 8
8 9 2
样例输出 复制
2 8

我的代码：
1.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N],b[N],n,x,m;
int main(){
    int ans[N]={};
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans[a[i]]=1;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++){
        cin>>b[i];
        
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=m;i++){
        if(ans[b[i]]==1){
            cout<<b[i]<<' ';
        }    
    }
        
    return 0;
}

2.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N],b[N],n,x,m;
int search(int n,int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            return mid;
        }else if(a[mid]>x) r=mid-1;
        else l=mid+1;
    } 
    return -1;
}
int main(){
    cin>>n>>m; 
    int l;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=m;i++){
        l=search(n,b[i]);
        if(l==-1){
        }else{
            cout<<a[l]<<" ";
        }
        l=0;
    }
    
    return 0;
}

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

在这个问题中，你需要找出安东诺夫在剧情模式中躲过的对局。你希望输出在输入的第一种情况下（躲过怀俄明号）中也存在的对局编号，并且按照输入顺序输出。

问题分析

我们有两组对局编号： - 第一组：躲过第一种劫难的对局编号（n个）。 - 第二组：躲过第二种劫难的对局编号（m个）。 我们的目标是找出两个集合之间的交集，并保持第一组的输出顺序。

输入输出格式

输入格式 1. 第一行：两个整数 n 和 m。 2. 第二行：n 个不重复的整数（第一组对局编号）。 3. 第三行：m 个不重复的整数（第二组对局编号）。 输出格式 输出在第一组中也存在于第二组的对局编号，按照第一组的输入顺序输出。

实现思路

1. 使用一个集合（set）存储第二组对局编号，以便于快速查找。
2. 遍历第一组对局编号，检查它们是否在集合中。
3. 如果在集合中，则输出该对局编号。

示例

假设输入为：

4 3
2 15 6 8
8 9 2

输出应为：

2 8

代码实现

下面是解决该问题的代码实现：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m; // 读入n和m
    vector<int> a(n), b(m);
    set<int> b_set; // 用于存储第二组对局编号
    // 读入第一组对局编号
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 读入第二组对局编号并存入集合
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        b_set.insert(b[i]); // 存储第二组对局编号到集合
    }
    // 遍历第一组对局编号，检查是否在集合中
    for (int i = 0; i < n; i++) {
        if (b_set.count(a[i])) { // 如果在第二组集合中
            cout << a[i] << " "; // 输出匹配的编号
        }
    }
    return 0;
}

代码解释

1. 读入 n 和 m，然后分别读取两组的对局编号。
2. 使用 set 存储第二组对局编号，方便后续查找。
3. 遍历第一组对局编号，使用 count 方法检查该编号是否在第二组中存在。
4. 如果存在，则打印该编号。

复杂度分析

• 构建 set 的时间复杂度为 O(m)。
• 对第一组进行遍历的时间复杂度为 O(n)。
• 总体时间复杂度为 O(n + m)。 如此代码能够高效地解决问题，且符合题目的要求。