Cinema

The first line of the input contains a positive integer n $(1 \leq n \leq 200 000)$ — the number of scientists.
The second line contains n positive integers $a_1,a_2, \dots ,a_n$ $(1 ≤a_i ≤ 10^9)$ , where aiis the index of a language, which the i-th scientist knows.
The third line contains a positive integer m $(1\leq m\leq 200 000)$ — the number of movies in the cinema.
The fourth line contains m positive integers $b_1,b_2,\dots,b_m$ $(1 ≤b_j ≤ 10^9)$ , where bjis the index of the audio language of the j-th movie.
The fifth line contains m positive integers $c_1,c_2, \dots,c_m$ $(1 ≤c_j ≤ 10^9)$ , where cj is the index of subtitles language of the j-th movie.
It is guaranteed that audio languages and subtitles language are different for each movie, that is $b_j \not= c_j$ .

Print the single integer — the index of a movie to which scientists should go. After viewing this movie the number of very pleased scientists should be maximum possible. If in the cinema there are several such movies, you need to choose among them one, after viewing which there will be the maximum possible number of almost satisfied scientists.
If there are several possible answers print any of them.

C++(g++ 7.5.0) 解法, 执行用时: 432ms, 内存消耗: 23080K, 提交时间: 2022-11-22 22:19:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int>mp;

int a[200005],b[200005];
int main(){
	int n,m,num1,num2,ans1=0,ans2=0,x,y,ans;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		mp[x]++;
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	cin>>a[i];
	for(int i=1;i<=m;i++)
	cin>>b[i];
	for(int i=1;i<=m;i++)
	{
		x=a[i],y=b[i];
		num1=mp[x];
		num2=mp[y];
		if(num1>ans1)
		ans=i,ans1=num1,ans2=num2;
		else if(num1==ans1&&num2>ans2)
		ans=i,ans1=num1,ans2=num2;
	}
	cout<<ans;
}

Python3 解法, 执行用时: 344ms, 内存消耗: 47808K, 提交时间: 2023-05-15 18:13:40

if __name__=='__main__':
    n=int(input())
    a=list(map(int,input().split()))
    m=int(input())
    b=list(map(int,input().split()))
    c=list(map(int,input().split()))
def test1():
    di=dict()
    for i in a:
        di[i]=di.get(i,0)+1
    weight=(di.get(b[0],0),di.get(c[0],0))
    res=0
    for i in range(1,m):
        t=(di.get(b[i],0),di.get(c[i],0))
        if t>weight:
            weight,res=t,i
    print(res+1)
if __name__=='__main__':
    test1()

C++14(g++5.4) 解法, 执行用时: 269ms, 内存消耗: 20584K, 提交时间: 2020-08-23 12:41:49

#include <cstdio>
#include<map>
using namespace std;
map<int,int> cnt;
int a[200005],ans,ans_a,ans_b,n;
int main() {
	scanf("%d",&n);
	for (int x; n; n--)
		scanf("%d",&x),cnt[x]++;
	scanf("%d",&n);
	for (int i=1; i<=n; i++) scanf("%d",&a[i]);
	
	for (int i=1,b; i<=n; i++) {
		scanf("%d",&b);
		if (cnt[a[i]]>ans_a || (cnt[a[i]]==ans_a && cnt[b]>ans_b))
			ans=i,ans_a=cnt[a[i]],ans_b=cnt[b];
	}
	printf("%d",ans);
	return 0;
}

C++ 解法, 执行用时: 358ms, 内存消耗: 17400K, 提交时间: 2022-04-17 12:43:03

#include<bits/stdc++.h>
using namespace std;
int n,m,x[200005],y,a[200005],p,q,ans=1;
map<int,int>cnt;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	cin>>x[i];
	for(int i=1;i<=m;i++)
	{
		cin>>y;
		if(cnt[x[i]]>p)
		{
			p=cnt[x[i]];
			ans=i;
		}
		else if(cnt[x[i]]==p)
		{
			if(cnt[y]>=q)
			{
				q=cnt[y];
				ans=i;
			}
		}
	}
	cout<<ans;
	return 0;
}

详情