电影

电影

莫斯科正在举办一个大型国际会议,有 $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$

输入样例

1
2
3
4
5
3
2 3 2
2
3 2
2 3

输出样例

1
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 )$

这个时间复杂度是可以过的,即使写的杂糅点时间也绰绰有余。

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!