我们要找看懂人数最多的电影,那就对于每个电影在a数组中寻找懂它的科学家数。
<algorithm>
里有两个二分查找函数upper_bound
和lower_bound
,前者返回数组中第一个大于查找值的下标,后者返回数组中第一个大于等于查找值的下标,两个下标做差即得到了等于查找值的个数。
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[200005],b[200005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",&b[i]);
int happiest=0,happy=0,ans=1;
for(int i=1,t;i<=m;++i)
{
scanf("%d",&t); //在线算省空间
int k1=upper_bound(a+1,a+n+1,b[i])-lower_bound(a+1,a+n+1,b[i]);
int k2=upper_bound(a+1,a+n+1,t)-lower_bound(a+1,a+n+1,t);
if(k1>happiest || (k1==happiest&&k2>happy)) happiest=k1,happy=k2,ans=i; //依题意模拟
}
printf("%d",ans);
return 0;
}