题目描述

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

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

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

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

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

对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影，可以让观影很开心的人最多。

如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

样例

3
2 3 2
2
3 2
2 3

输出:

2

算法1

(离散化+排序)

这题需要先统计每部电影的能让科学家看懂的数量（听懂语音或者看懂字幕），然后根据题意，应该把电影先根据语音从大到小排，再根据字幕从大到小排。

这题可以只对科学家懂得语言进行排序和离散化（也就是去重），同时用一个数组记录每种语言懂得科学家人数。然后在读入每部电影语音和字幕的时候查找对应语言的编号，然后加上对应的人数。最后再对电影排序。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

int n, m;
const int maxn = 2e5 + 10;
LL a[maxn], b[maxn];//b保存去重后的数据
int cnt = 0;
LL aa[maxn];//保存去重之后每个数字重复的次数

struct Node {
    LL idx;
    LL s1, s2;//s1代表语音,s2代表字幕
}nodes[maxn];


bool cmp(Node n1, Node n2) {
    if (n1.s1 != n2.s1)return n1.s1 > n2.s1;
    return n1.s2 > n2.s2;
}

//去重
void get_unique(LL arr[], int k) {
    sort(arr + 1, arr + k + 1);//先排序
    for (int i = 1, j = i; i <= k; ) {
        while (j<=k && arr[j] == arr[i]) {
            j++;
        }
        b[++cnt] = a[j - 1];
        aa[cnt] = j - i;//统计人数
        i = j;
    }
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    get_unique(a, n);//去重

    LL tmp;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {//初始化电影编号
        nodes[i].idx = i;
    }

    for (int i = 1; i <= m; i++) {//语音
        scanf("%lld", &tmp);
        int idx = lower_bound(b + 1, b + cnt + 1, tmp) - b;
        //lower_bound找的是第一个大于等于tmp的数的下标,可能不是等于是大于,也可能超过数组范围
        // 所以需要判断找到的是否和tmp相等
        if (idx <= m && b[idx] == tmp)nodes[i].s1 += aa[idx];
    } 
    for (int i = 1; i <= m; i++) {//字幕
        scanf("%lld", &tmp);
        int idx = lower_bound(b + 1, b + cnt + 1, tmp) - b;
        if (idx <= m && b[idx] == tmp)nodes[i].s2 += aa[idx];
    } 

    sort(nodes + 1, nodes + 1 + m, cmp);
    printf("%lld", nodes[1].idx);

    return 0;
}