算法竞赛进阶指南 电影

原题目链接

问题描述

莫斯科正在举办一个大型国际会议，有 n 个来自不同国家的科学家参会。

每个科学家只懂得一种语言。

为了方便起见，我们将世界上的所有语言用 1 到 10^9 之间的整数编号。

在会议结束后，所有科学家决定一起去看一场电影放松一下。

电影院里一共有 m 部电影正在上映，每部电影的语音语言和字幕语言都不同。

对于观影的科学家：

• 如果能听懂电影的语音语言，他会 很开心；
• 如果不能听懂语音语言但能看懂字幕语言，他会 比较开心；
• 如果两者都不懂，他会 不开心。

现在科学家们决定大家一起看同一部电影，请你帮忙选择一部电影，使得：

• 很开心的人数最多；
• 如果有多部电影满足条件，则从中选择 比较开心的人数最多 的那一部。

输入格式

• 第 1 行：一个整数 n，表示科学家的数量。
• 第 2 行：n 个整数 a₁, a₂, ..., aₙ，表示第 i 个科学家懂得的语言编号。
• 第 3 行：一个整数 m，表示电影的数量。
• 第 4 行：m 个整数 b₁, b₂, ..., bₘ，表示第 i 部电影的语音语言编号。
• 第 5 行：m 个整数 c₁, c₂, ..., cₘ，表示第 i 部电影的字幕语言编号。

对于同一部电影，保证 bᵢ ≠ cᵢ。

所有数字在同一行内用空格隔开。

输出格式

输出一个整数，表示最终选择的电影编号，编号从 1 到 m。

如果有多个答案，输出其中任意一个均可。

数据范围

• 1 ≤ n, m ≤ 200000
• 1 ≤ aᵢ, bᵢ, cᵢ ≤ 10^9

输入样例

3
2 3 2
2
3 2
2 3

输出样例

2

c++代码

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

int n, a, b, c, good = 0, middle = 0, k, w, ans = 1, m;
int voice[200001], title[200001];
unordered_map<int, int> mp;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        mp[a]++;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &voice[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &title[i]);
    }
    for (int i = 1; i <= m; i++) {
        k = mp.find(voice[i]) == mp.end() ? 0 : mp[voice[i]];
        w = mp.find(title[i]) == mp.end() ? 0 : mp[title[i]];
        if (k > good || (k == good && w > middle)) {
            good = k;
            middle = w;
            ans = i;
        }
    }
    printf("%d", ans);
    return 0;
}//by wqs