题目描述
莫斯科正在举办一个大型国际会议,有n个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见,我们把世界上的所有语言用1到109之间的整数编号。
在会议结束后,所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有m部电影正在上映,每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说,如果能听懂电影的语音,他就会很开心;如果能看懂字幕,他就会比较开心;如果全都不懂,他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影,可以让观影很开心的人最多。
如果有多部电影满足条件,则在这些电影中挑选观影比较开心的人最多的那一部。
输入格式
第一行输入一个整数n,代表科学家的数量。
第二行输入n个整数a1,a2…an,其中ai表示第i个科学家懂得的语言的编号。
第三行输入一个整数m,代表电影的数量。
第四行输入m个整数b1,b2…bm,其中bi表示第i部电影的语音采用的语言的编号。
第五行输入m个整数c1,c2…cm,其中ci表示第i部电影的字幕采用的语言的编号。
请注意对于同一部电影来说,bi≠ci。
同一行内数字用空格隔开。
输出格式
输出一个整数,代表最终选择的电影的编号。
如果答案不唯一,输出任意一个均可。
数据范围
1≤n,m≤200000,
1≤ai,bi,ci≤109
样例
输入样例:
3
2 3 2
2
3 2
2 3
输出样例:
2
算法
这东西我没用map(划重点)
(简单的)主要是手写离散化,然后随随便便lower_bound一下
在这里有几个点要注意:
- 看清题意(一开始眼抽以为是都开心,就找了都开心的加了起来结果没想到对了13/14的测试点???)
- 注意了(敲黑板ing)lower_bound出来的排名不一定在数组中出现过所以要注意特判一下
- 额,简单的记两个变量在更新答案的时候的小操作
- 好啦,都是常规操作
时间复杂度
复杂度的话也是mlogn+nlogn的,主要是锻炼一下上述的常规操作
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define maxn 300000
int n;
int a[maxn],b[maxn],c[maxn],na[maxn],aa[maxn];
int ans1,ans2;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1]){
na[++cnt]=1;
aa[cnt]=a[i];
}
else{
na[cnt]++;
}
}
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
}
int ans=0;int answer=0;
for(int i=1;i<=m;i++){
int res1=0;int res2=0;
int x=lower_bound(aa+1,aa+1+cnt,b[i])-aa;
if(aa[x]!=b[i]) x=0;
res1=na[x];
x=lower_bound(aa+1,aa+1+cnt,c[i])-aa;
if(aa[x]!=c[i]) x=0;
res2=na[x];
// cout<<res1<<" "<<res2<<endl;
if(res1>ans){
ans=res1;
ans2=res2;
answer=i;
}
else if(res1==ans){
if(res2>ans2){
ans2=res2;
answer=i;
}
}
}
printf("%d",answer);
return 0;
}
tql%%%