【题目来源】
https://www.acwing.com/problem/content/105/

【题目描述】
莫斯科正在举办一个大型国际会议，有 n 个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见，我们把世界上的所有语言用 1 到 10^9 之间的整数编号。
在会议结束后，所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有 m 部电影正在上映，每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

【输入格式】
第一行输入一个整数 n，代表科学家的数量。
第二行输入 n 个整数 a1, a2, …, an，其中 ai 表示第 i 个科学家懂得的语言的编号。
第三行输入一个整数 m，代表电影的数量。
第四行输入 m 个整数 b1, b2, …, bm，其中 bi 表示第 i 部电影的语音采用的语言的编号。
第五行输入 m 个整数 c1, c2, …, cm，其中 ci 表示第 i 部电影的字幕采用的语言的编号。
请注意对于同一部电影来说，bi≠ci。
同一行内数字用空格隔开。

【输出格式】
输出一个整数，代表最终选择的电影的编号。电影编号 1∼m。
如果答案不唯一，输出任意一个均可。

【数据范围】
1≤n,m≤200000,
1≤ai,bi,ci≤10^9

【输入样例】
3
2 3 2
2
3 2
2 3

【输出样例】
2

【算法分析】
● 简单而言，常用的离散化算法步骤为“提取、排序、去重、映射”。虽然，离散化算法的实现有多种方法，但是个人认为，利用 STL map 实现的离散化代码，最是简单易懂。
● STL map → https://blog.csdn.net/hnjzsyjyj/article/details/146118701
● 离散化是一种数据处理的技巧。可以进行离散化的数据有大整数、浮点数、字符串等。
● 对元素为 pair 的数组的各元素进行排序的方法：https://blog.csdn.net/hnjzsyjyj/article/details/143902071
默认按 pair 数组元素的 first 域进行非递减排序。若 first 域相同，则按 pair 数组元素的 second 域进行非递减排序。

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=1e5+5;
typedef pair<int,int> PII;
PII v[maxn];
 
int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>v[i].first>>v[i].second;
    }
    sort(v,v+n);
    for(int i=0; i<n; i++) {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;
}
 
/*
in:
5
5 8
3 1
2 9
1 6
5 3

out:
1 6
2 9
3 1
5 3
5 8
*/

【算法代码一：数组 + sort + STL map】

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int maxn=2e5+5;
int b[maxn],c[maxn];
map<int,int> mp;
int n,m;

int main() {
    cin>>n;
    while(n--) { //discretization
        int x;
        cin>>x;
        mp[x]++;
    }

    cin>>m;
    for(int i=1; i<=m; i++) cin>>b[i];
    for(int i=1; i<=m; i++) cin>>c[i];

    int idx=1;
    PII u={0,0};
    for(int i=1; i<=m; i++) {
        PII t={mp[b[i]],mp[c[i]]};
        if(u<t) u=t,idx=i;
    }
    cout<<idx<<endl;

    return 0;
}

/*
in:
3
2 3 2
2
3 2
2 3

out:
2
*/

【算法代码二：数组 + sort + vector】

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5, M=N*3;
int a[N],b[N],c[N],cnt[M];
vector<int> v;
int n,m;

int find(int x) {
    int le=0, ri=v.size()-1;
    while(le<ri) {
        int mid=le+ri>>1;
        if(v[mid]>=x) ri=mid;
        else le=mid+1;
    }
    return ri;
}

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

    scanf("%d",&m);
    for(int i=1; i<=m; i++) {
        scanf("%d",&b[i]);
        v.push_back(b[i]);
    }
    for(int i=1; i<=m; i++) {
        scanf("%d",&c[i]);
        v.push_back(c[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i=1; i<=n; i++) {
        int x=find(a[i]);
        cnt[x]++;
    }

    int ans=1, mx1=0, mx2=0;
    for(int i=1; i<=m; i++) {
        int x=find(b[i]), y=find(c[i]);
        int cnt1=cnt[x], cnt2=cnt[y];
        if(cnt1>mx1 || (cnt1==mx1 && cnt2>mx2)) {
            ans=i;
            mx1=cnt1;
            mx2=cnt2;
        }
    }
    printf("%d\n",ans);
    return 0;
}


/*
in:
3
2 3 2
2
3 2
2 3

out:
2
*/

【参考文献】
https://www.acwing.com/solution/content/22662/
https://www.acwing.com/solution/content/195136/
https://www.acwing.com/solution/content/174428/
https://blog.csdn.net/hnjzsyjyj/article/details/130179373
https://blog.csdn.net/hnjzsyjyj/article/details/143275575
https://blog.csdn.net/hnjzsyjyj/article/details/143309807
https://blog.csdn.net/hnjzsyjyj/article/details/143315085