电影
原题链接
具体离散化的用处—>传送门
给出一堆科学家擅长的语言，给出电影，电影有科学家喜欢的，一般的，否则都不喜欢，进行匹配，将所有信息放到一个数组里，排序去重离散化，再用科学家的信息去二分查找匹配用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;
}
