题目传送门
【题目大意】
有$N$个科学家，第$i$个科学家懂得编号为$a_i$的语言，现在有$M$部电影，每部电影有一个声音语言和字幕语言，且保证同一部电影的里两种语言不同，求使得听懂电影语言的人数最多且看懂电影语言的人数最多(即如果第一个条件相同，取第二个条件)的电影编号。
【思路分析】
语言的编号范围在$1～10^9$，所以无法直接统计懂得某种语言的科学家人数，如果要一个个统计的话复杂度会达到$O(NM)$，也过不了，所以我们考虑离散化。
$M$部电影和$N$个科学家，最多涉及$M*2+N$种语言，所以我们可以把出现的每种语言用$1～M*2+N$中的一个数表示，然后用数组直接统计懂得每种语言的科学家数量，再判断。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define rg register 5 #define go(i,a,b) for(rg int i=a;i<=b;i++) 6 using namespace std; 7 const int N=200002; 8 int n,m,a[N],b[N],c[N],d[N*3],num_a[N]; 9 int e[N*3],num,max1,max2,id=1,t=0; 10 void discrete(){ 11 sort(d+1,d+1+t); 12 go(i,1,t) 13 if(i==1||d[i]!=d[i-1]) e[++num]=d[i]; 14 return; 15 } 16 int query(int x){ 17 int l=1,r=num,mid; 18 while(l<r){ 19 mid=(l+r)>>1; 20 if(e[mid]>=x) r=mid; 21 else l=mid+1; 22 } 23 return l; 24 } 25 int main(){ 26 scanf("%d",&n); 27 go(i,1,n) scanf("%d",&a[i]),d[++t]=a[i]; 28 scanf("%d",&m); 29 go(i,1,m) scanf("%d",&b[i]),d[++t]=b[i]; 30 go(i,1,m) scanf("%d",&c[i]),d[++t]=c[i]; 31 discrete(); 32 go(i,1,n) num_a[query(a[i])]++; 33 go(i,1,m){ 34 int s1=num_a[query(b[i])],s2=num_a[query(c[i])]; 35 if(max1<s1||(max1==s1&&max2<s2)) max1=s1,max2=s2,id=i; 36 } 37 cout<<id<<endl; 38 return 0; 39 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11248240.html
相关资源：JAVA上百实例源码以及开源项目