莫斯科在举办一场重要的有 $n$ 个不同国家的珂学家参与的国际会议，每个珂学家都只会一种语言。为了方便起见，我们规定一种语言用 $1$ 到 $10^9$ 的数来描述。
在会议之后的晚上，珂学家们决定去看电影。他们去的电影院有 $m$ 场电影，每场有两个不同的数字，分别代表配音的语言和字幕的语言。
如果一个珂学家能听懂配音，他会非常愉悦；如果能看懂字幕，他会比较满意。
如果既看不懂也听不懂，他会很生气。 珂学家们决定去看同一场电影，你必须帮助他们选择一场电影，让愉悦的人最多的前提下，比较满意的人最多。

输入格式：
第一行一个整数 $n(1≤n≤200000)$ 表示珂学家个数。
第二行n个整数 $a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)$ 表示珂学家们会的语言。
第三行一个整数 $1≤m≤200000$ 表示电影的场数。
第四行m个整数 $b_1,b_2,...,b_n(1 \leq b_j \leq 10^9)$ 表示电影的配音用的语言。 第五行 $m$ 个整数 $c_1,c_2,...,c_n(1 \leq c_j \leq 10^9)c$ 表示电影的字幕用的语言。

输出格式：
一个整数表示安排哪一场电影。 如果有多种情况，选择比较满意的方案输出。

解题思路

由于数据范围过大，一次性统计个数肯定会爆，而珂学家的个数只有2e5个，所以我们可以想到用离散化做。
离散化的目标：在大小关系不变的情况下，将数值范围压缩。
离散化的过程：先排序（这里改变了顺序），然后压缩，最后还原顺序。
例如将1 8 3 20004131 213513离散化：
1.排序：1 3 8 213513 20004131
2.压缩：1 2 3 4 5
3.还原：1 3 2 5 4
核心代码：

void discrete(){
    tmp=0;
    for(int i=1;i<=n;i++){
        mem[i]=a[i];//用于保存原来的顺序
    }
    sort(a+1,a+n+1);//排序
    //压缩
    for(int i=1;i<=n;i++){
        if(i==1||a[i]!=a[i-1]){
            b[++tmp]=a[i];
        }
    }
    return ;
}
void solve(){//还原
    for(int i=1;i<=n;i++){
        ans[i]=lower_bound(b+1,b+tmp+1,mem[i])-b;
    }
}

代码

#include<bits/stdc++.h>
using namespace std;
int lang[600005];
int a[600005];
int n,m;
int b[600005];
int lc[600005];
int ac[600005];
int accept[200005],like[200005];
int tmp;
int mem[600005];
//将所有语言都归并起来并且压缩
void discrete(){
    sort(lang+1,lang+n+2*m+1);
    for(int i=1;i<=n+2*m;i++){
        if(i==1||lang[i]!=lang[i-1]){
            b[++tmp]=lang[i];
        }
    }
    return ;
}
//还原并且统计每个语言会的人数
void solve(){
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+tmp+1,mem[i])-b;
        lc[a[i]]++;
        ac[a[i]]++;
    }
    for(int i=1;i<=m;i++){//还原较为满意与非常愉悦的语言
        like[i]=lower_bound(b+1,b+tmp+1,like[i])-b;
        accept[i]=lower_bound(b+1,b+tmp+1,accept[i])-b;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>lang[i];
        mem[i]=lang[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>like[i];
        lang[i+n]=like[i];
    }
    for(int i=1;i<=m;i++){
        cin>>accept[i];
        lang[i+m+n]=accept[i];
    }
    discrete();
    solve();
    int Max=0,Maxn=1,Maxa=0;
    for(int i=1;i<=m;i++){
        if(lc[like[i]]>Max){
            Max=lc[like[i]];
            Maxn=i;
            Maxa=ac[accept[i]];
        }else if(lc[like[i]]==Max){
            if(ac[accept[i]]>Maxa){
                Maxn=i;
                Maxa=ac[accept[i]];
            }
        }
    }
    cout<<Maxn;
    return 0;
}

本文链接：https://kaispace.com.cn/index.php/archives/467/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者