题目描述

有m部正在上映的电影，每部电影的语音和字幕都采用不同语言，用一个int范围内的整数表达语言。有n个人相约一起去看其中一部电影，每个人只会一种语言，如果一个人能听懂电影的语音，他会很高兴；如果能看懂字幕，他会比较高兴；如果语音和字幕都不懂，他会不开心。请你选择一部电影让这n个人一起看，使得很高兴的人最多。如果很高兴人数最多的电影有好几部，选择比较高兴的人最多。如果答案还不唯一，输出最小编号的答案。

输入

第一行输入n (1<=n<=200000)，表示有n个人
接下来一行输入n个整数，表示每个人所会的语言ai, (1<=ai<=10^9)
接下来输入m (1<=m<=200000)，表示电影数量
接下来一行输入m个整数，表示每部电影语音的语言bj(1<=bj<=10^9)
接下来一行输入m个整数，表示每部电影字幕的语言cj(1<=cj<=10^9，且bj和cj不同)

输出

输出编号最小的答案

样例输入

3
2 3 2
2
3 2
2 3

样例输出

2

样例输入2:

6 
6 3 1 1 3 7 
5 
1 2 3 4 5 
2 3 4 5 1 

样例输出2:

1 

思路

因为语言的取值很大,但数据不多,所以可以离散化后映射,用logn的时间进行查询

代码

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

struct node{
    int a,b,id;
}mo[200005];

int a[200005],sum[600005],t[600005],cnt,b,n,m,ans1=-1,ans2,ansid;

void init(){
    sort(t+1,t+cnt+1);  //排序
    cnt=unique(t+1,t+cnt+1)-(t+1);  //去重
}

int find(int x){
    int tmp=lower_bound(t+1,t+cnt+1,x)-t;  //查找
    return tmp;
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        t[++cnt]=a[i];
    }
    cin>>m;
    for (int i=1;i<=m;++i){
        int tmp;
        scanf("%d",&tmp);
        mo[i].a=tmp;
        t[++cnt]=tmp;
    }
    for (int i=1;i<=m;++i){
        int tmp;
        scanf("%d",&tmp);
        mo[i].b=tmp;
        t[++cnt]=tmp;
    }
    init();
    for (int i=1;i<=n;++i){
        sum[find(a[i])]++;
    }
    for (int i=1;i<=m;++i){
        int tmp=sum[find(mo[i].a)];
        int tmp2=sum[find(mo[i].b)];
        if (tmp>ans1){
            ans1=tmp;
            ans2=tmp2;
            ansid=i;
        }else if(tmp==ans1 && tmp2>ans2){
            ans2=tmp2;
            ansid=i;
        }
    }
    cout<<ansid<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/54/