題目

莫斯科正在舉辦一個大型國際會議，有 $n$ 個來自不同國家的科學家參會。

每個科學家都只懂得一種語言。
為了方便起見，我們把世界上的所有語言用 1 到 109 之間的整數編號。

在會議結束后，所有的科學家決定一起去看場電影放松一下。

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

對于觀影的科學家來說，如果能聽懂電影的語音，他就會很開心；如果能看懂字幕，他就會比較開心；如果全都不懂，他就會不開心。

現在科學家們決定大家看同一場電影。

請你幫忙選擇一部電影，可以讓觀影很開心的人最多。

如果有多部電影滿足條件，則在這些電影中挑選觀影比較開心的人最多的那一部。

輸入格式

第一行輸入一個整數 $n$，代表科學家的數量。

第二行輸入 $n$ 個整數 $a_1,a_2\dots a_n$，其中 $a_i$ 表示第 $i$ 個科學家懂得的語言的編號。

第三行輸入一個整數 $m$，代表電影的數量。

第四行輸入 $m$ 個整數 $b_1,b_2\dots b_m$，其中 $b_i$ 表示第 $i$ 部電影的語音采用的語言的編號。

第五行輸入 $m$ 個整數 $c_1,c_2\dots c_m$，其中 $c_i$ 表示第 $i$ 部電影的字幕采用的語言的編號。

請注意對于同一部電影來說，$b_i\ne c_i$。

同一行內數字用空格隔開。

輸出格式

輸出一個整數，代表最終選擇的電影的編號。電影編號 1～$m$。

如果答案不唯一，輸出任意一個均可。

數據范圍

• $1\le n,m\le 200000$
• $1\le a_i,b_i,c_i\le 10^9$

輸入樣例

3
2 3 2
2
3 2
2 3

輸出樣例

2

分析

雖然語言的范圍在 int 以內，但是這 $m$ 部電影與 $n$ 個人最多涉及 $2?m+n$ 種語言。把所有電影和人涉及的語言放入一個數組中，排序并離散化，用一個 1 ~ $2?m+n$ 之間的整數代替每種語言。此時就可以用數組直接統計會上述每種語言的人的數量，從而選擇滿足題目要求的電影。

時間復雜度為 $O((n+m)log(n+m))$。

代碼

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 2e5 + 50;
int a[N], b[N], c[N];
int cinema[N * 3];
int tot = 0;
int k = 0;
int ans[N * 3];//查詢x映射為哪個1~k之間的整數
int query(int x) {return lower_bound(cinema + 1, cinema + 1 + k, x) - cinema;
}//離散化
void discrete() {//排序sort(cinema + 1, cinema + tot + 1);//去重，k為去重后的元素個數k = unique(cinema + 1, cinema + tot + 1) - (cinema + 1);
}int main() {int n, m;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];cinema[++tot] = a[i];}cin >> m;for (int i = 1; i <= m; i++) {cin >> b[i];cinema[++tot] = b[i];}for (int i = 1; i <= m; i++) {cin >> c[i];cinema[++tot] = c[i];}//離散化discrete(); for (int i = 1; i <= n; i++) ans[query(a[i])]++; //統計每種語言會的科學家數//遍歷所有電影//res 為最終結果，初始值為1，是因為如果沒有符合條件的電影就隨便選擇一部，電影編號是從1開始的int res = 1, ans1 = 0, ans2 = 0;for (int i = 1; i <= m; i++) {int ansb = ans[query(b[i])]; //能聽懂電影的語音的人數——>開心int ansc = ans[query(c[i])]; //能看懂字幕的人數--> 比較開心//當前電影比之前的電影開心的人多 或者 開心的人和之前的人一樣，但是比較開心的比之前多，則選擇當前電影if (ansb > ans1 || (ansb == ans1 && ansc > ans2)) { res = i;ans1 = ansb;ans2 = ansc;}}cout << res << endl;return 0;
}