离散化专题

Acwing:103电影

https://www.acwing.com/problem/content/105/

题意：

有m步电影，有m种字幕语言、m种音频语言，n个人会n个语言去看，要找到一种m、m、n的组合使得看得懂的人最多，其中听懂语音很高兴，看懂字幕较高兴，要让很高兴的人为第一指标，较高兴为第二指标，最优化结果。

分析：

    首先：我为什么要用离散化？每个语言数据都是1e9级别，暴力来解决的话。1：我要找到所有电影音频的会的科学家人数。2：所有电影字幕会的科学家人数。3：最后以音频人数最多，字幕其次的顺序取最优值。

    而我们在统计科学家人数的时候是要看这个语言的位置上有几个人，也就是st[语言i]=？，而这个语言数有1e9的数量级，这个坑位会开得很大，如果用离散化把这1e9的坑位转成稠密的话，就可以快速访问计数

1：总共有涉及m+m+n种语言，选取一种语言使结果最优。2：把所有语言存到数组中离散化，用1-2m+n的整数代表所有语言。3：统计上述语言的满足人数。

代码思想：

1：所有语言读入用lan[++cnt]=a[i]/b[i]/c[i]记录，用一个顺序的数组记录。

2：因为每种语言读入会出现重复操作，去重可以用sort排序一遍然后判断相邻的位置是否相同来去重。

for(int i=1;i<=tot;i++){
        if(i==1 || lang[i]!=lang[i-1]){
            uni[++k]=lang[i];
        }
    }

3：离散化科学家会的语言，之后方便每部电影去找

//find作用是把稀疏编号转为稠密编号
int find(int x){
    return lower_bound(uni+1,uni+1+k,x)-uni;
}//把x值在uni离散化后的数组中的位置返回，存在现在的新坑中
for(int i=1;i<=n;i++) ans[find(a[i])]++;//存到ans新坑里

4：最后枚举所有电影的音频和字幕适配的人数，取max。

#include 
#include 
using namespace std;
int n,m,k=0,tot=0;
const int N=2e5+50;
//3*N是因为语言的来源有3个地方，假设都不相同，则有3*N种语言
int lang[3*N],uni[3*N],a[N],b[N],c[N],ans[3*N];
//find作用是把稀疏编号转为稠密编号
int find(int x){
    return lower_bound(uni+1,uni+1+k,x)-uni;
}
 
int main(){
    //保存科学家会的语言，并用lang记录
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        lang[++tot]=a[i];
    }
    //保存电影音频的语言，并用lang记录
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
        lang[++tot]=b[i];
    }
    //保存电影字幕的语言，并用lang记录
    for(int i=1;i<=m;i++){
        scanf("%d",&c[i]);
        lang[++tot]=c[i];
    }
    //排序lang，为了去重复
    sort(lang+1,lang+1+tot);
    //把lang数组去重复，保存到uni数组
    //uni的数组下标做为每种语言(原有的1-10^9的稀疏编号）新的稠密编号
    for(int i=1;i<=tot;i++){
        if(i==1 || lang[i]!=lang[i-1]){
            uni[++k]=lang[i];
        }
    }
    //a[i]中保存原始的稀疏编号，用find转变成稠密编号，并用ans数组记录每种语言出现的次数。
    for(int i=1;i<=n;i++) ans[find(a[i])]++;
    //遍历所有电影，按要求找到最多科学家会的电影
    int ans0,ans1,ans2;
    //ans0保存最终结果，ans1和ans2为中间结果
    ans0=ans1=ans2=0;
    for(int i=1;i<=m;i++){
        //算出第i个电影音频语言的科学家数，和第i个字幕语言的科学家数
        int anx=ans[find(b[i])],any=ans[find(c[i])];
        //如果ans大于ans1或者前者相等且any大于ans2时，更新
        if(anx>ans1 || (anx==ans1 && any>ans2)){
            ans0=i,ans1=anx,ans2=any;
        }
    }
    //如果所有的电影的声音和字幕的语言，科学家们都不懂，随便选一个
    if(ans0==0){
        printf("%d\n",1);
    }else{
        printf("%d\n",ans0);
    }
 
    return 0;
}