电影
莫斯科正在举办一个大型国际会议,有 $n$ 个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见,我们把世界上的所有语言用 $1$ 到 $10^9$ 之间的整数编号。
在会议结束后,所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有 $m$ 部电影正在上映,每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说,如果能听懂电影的语音,他就会很开心;如果能看懂字幕,他就会比较开心;如果全都不懂,他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影,可以让观影很开心的人最多。
如果有多部电影满足条件,则在这些电影中挑选观影比较开心的人最多的那一部。
输入格式
第一行输入一个整数 $n$,代表科学家的数量。
第二行输入 $n$ 个整数 $a_1,a_2…a_n$,其中 $a_i$表示 第 $i$ 个科学家懂得的语言的编号。
第三行输入一个整数 $m$,代表电影的数量。
第四行输入 $m$ 个整数 $b_1,b_2…b_m$,其中 $b_i$ 表示第 $i$ 部电影的语音采用的语言的编号。
第五行输入 $m$ 个整数 $c_1,c_2…c_m$,其中 $c_i$表示第 $i$ 部电影的字幕采用的语言的编号。
请注意对于同一部电影来说,$b_i≠c_i$。
同一行内数字用空格隔开。
输出格式
输出一个整数,代表最终选择的电影的编号。电影编号 $1∼m$。
如果答案不唯一,输出任意一个均可。
数据范围
$1≤n,m≤200000$,
$1≤a_i,b_i,c_i≤10^9$
输入样例
3
2 3 2
2
3 2
2 3
输出样例
2
解析
只考虑电影的语言和字幕是否和科学家会的语言一样,看到询问的数据范围 $2 \times 10^5$,而每个数的大小却是 $1 \times 10^9$ 那么久考虑使用离散化。
离散化是指,将一段稀疏的数据变成一段稠密的数据
对应题意,有一个最简单的实现方法,假设会的语言编号为 2 8 1000 100000,那么就可以得到 $f_2 = …,f_8 = …,f_{1000} = …,f_{100000}=…$ 这里的 $f_i$ 为每种语言有多少科学家会,于是我们询问时直接提取就好,但是有个问题 这里编号大小的数据范围为 $[1,10^9]$,直接开这么大的数组就会 MLE。于是考虑离散化
例如,假设我的原数组是 2 8 1000 100000,那么我的新数组就是 1 2 3 4,为了在询问原数组的数时能快速得到新数组的对应值,我们用另外一个数组来储存原数组 即 $a_i$,那么可得 $a_1 = 2,a_2 = 8, a_3 = 1000, a_4 = 100000$ ,该数组满足单调性,那么用二分在这个数组里查询就可以很快得到新数组的值(即查询的下标)。
我们的原问题也可以得到解决,此时我们的 $f_i$ 就变成了 $f_1 = …,f_2 = …,f_3 = …,f_4 = …$ ,离散化后的下标数据范围为 $[1, 2\times 10^5]$ ,很显然 这样开就不会MLE了。
既然不会 MLE 了,我们再来算下时间复杂度。假设总共有 $K$ 种语言,那么每次询问用二分来查询就是 $O(logK)$ 的复杂度,单独查询电影语言的总复杂度就是 $O(mlogK)$,而二分查询需要满足一定的二分性,且科学家的顺序并不影响我们之后的操作,所以我们统计科学家语言的时候只需要将其排序再统计,那么可得总复杂度就是 $O(nlogn +2mlogK )$
这个时间复杂度是可以过的,即使写的杂糅点时间也绰绰有余。
看代码
#include <cstdio>
#include <iostream>
#include <algorithm>
//不想用map和set 也不想记二分函数 那样就不会计算时间复杂度了
//代码写的有点复杂了,懒得优化 看个思路就好 自己写
const int N = 200005;
int arr[N], Sign[N], Newarr[N], RSign[N], answ[N];
bool Vis[N];
int tnt = 1, tot = 0;
int cheak(int x) { //二分寻找离散化之前的原值
int l = 1, r = tot;
while(r >= l) {
int mid = (l + r) >> 1;
if(x == Sign[mid]) return mid;
else if(x > Sign[mid]) l = mid + 1;
else r = mid - 1;
} return 0;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
std::sort(arr + 1, arr + 1 + n);
for (int i = 1; i <= n; i++) { //统计每种语言有多少科学家会,离散化原数组
if(arr[i] == arr[i + 1]) Newarr[tnt]++;
else Newarr[tnt]++, tnt++;
if(arr[i] != arr[i + 1]) Sign[++tot] = arr[i];
}
int m, ans = 0, ansx, maxx = 0, twt = 0; bool flag = false;
scanf("%d", &m);
for (int i = 1; i <= m; i++) { //询问电影语言
int x;
scanf("%d", &x); RSign[i] = x;
ansx = cheak(x); if(ansx == 0) continue;
if(maxx < Newarr[ansx]) {
//因为可能存在多个听得懂语言的科学家数量相同的电影 所以需要记录
maxx = Newarr[ansx];
ans = i;
twt = 1;
answ[twt] = i;
} else if(maxx == Newarr[ansx]) {
twt++;
answ[twt] = i;
}
} if(ans == 0) flag = true;
//如果所有科学家都听不懂,那么我们就标记 等会儿就只考虑看得懂
for (int i = 1; i <= twt; i++) Vis[answ[i]] = true; //方便调用
int ansy, maxy = 0;
for (int i = 1; i <= m; i++) { //询问电影字幕
int y;
scanf("%d", &y);
ansy = cheak(y); if(ansy == 0) continue;
if(flag && maxy <= Newarr[ansy]) maxy = Newarr[ansy], ans = i;
if(!flag && Vis[i] && maxy <= Newarr[ansy]) {
maxy = Newarr[ansy];
ans = i;
}
} if(ans == 0) printf("%d\n", m); else printf("%d\n", ans);
//如果没有一部电影是科学家们看得懂和听得懂的 我们就随便输出一个(也满足题意)
return 0;
}