离散化

电影

原题链接

具体离散化的用处—>传送门

给出一堆科学家擅长的语言，给出电影，电影有科学家喜欢的，一般的，否则都不喜欢，进行匹配，将所有信息放到一个数组里，排序去重离散化，再用科学家的信息去二分查找匹配用sum数组记录，最后优先让喜欢的匹配的多，其次是比较喜欢的

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e6+10;

int a[N],b[N],c[N];
int arr[3*N],cnt[3*N],sum[3*N];
int n,t=0,mm=0,m;

//离散化
void discrete()
{
    sort(arr+1,arr+t+1);
    for(int i=1;i<=t;i++)
    {
        if(i==1||arr[i]!=arr[i-1])
            cnt[++mm]=arr[i];
    }
}

//二分查找离散化的位置
int query(int x)
{
    return lower_bound(cnt+1,cnt+mm+1,x)-cnt;
}


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        arr[++t]=a[i];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        arr[++t]=b[i];
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&c[i]);
        arr[++t]=c[i];
    }
    //离散化
    discrete();
    //二分查找统计
    for(int i=1;i<=n;i++)//统计每种语言的人的数量
    {
        int id=query(a[i]);
        ++sum[id];
    }
    //开始匹配
    //bmax很高兴的人多,cmax让比较开心的人多
    int bmax=-1,cmax=-1,ans=0;
    for(int i=1;i<=m;i++)
    {
        int s1=query(b[i]);
        int s2=query(c[i]);
        if(sum[s1]>bmax)//高兴的人多的情况下就选
        {
            bmax=sum[s1];
            cmax=sum[s2];
            ans=i;
        }
        else if(sum[s1]==bmax&&sum[s2]>cmax)//高兴的人相同时，就选比较开心的人多的那边
        {
            bmax=sum[s1];
            cmax=sum[s2];
            ans=i;
        }
    }
    printf("%d\n",ans);
    return 0;
}