题解：B4277 [蓝桥杯青少年组国赛 2023] 主要成分

前言

居然这么简单的题目无人交题解，那我就来交一发吧。

正言

首先，要所含的化学成分超过一半，那我们是不是能开一个桶来储存，但是，因为输入最大达到了

2 \times 10^9

，我们不能开一个数组来储存，所以我们用 map 来储存。

如果你这样子交上去的话，你只有

80

分，为什么呢？因为 map 时间复杂度太高了。

所以我们重新想，想要求出一个数在序列里出现的次数，还要时间复杂度够快，这里有一种思路，我们排序，求一个数连续出现了多少次，然后统计一下最大出现次数就好了。

代码

80分

CPP

//By Wide_Master
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int>s;
int n,h,a[1000005],maxv=-1,maxl=-1;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	h=n/2; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(s[a[i]]>=h){
			if(s[a[i]]>maxl){
				maxl=s[a[i]];
				maxv=a[i];
			}
		}
	}
	if(maxv!=-1)cout<<maxv<<endl;
	else puts("No");
	return 0;
}

100分

CPP

//By Wide_Master
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int>s;
int n,h,a[1000005],maxv=-1,maxl=-1;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	h=n/2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=2,len=1;i<=n;i++){
		if(a[i]==a[i-1]){
			len++;
		}else{
			if(len>=h&&len>maxl){
				maxl=len;
				maxv=a[i-1];
			}
			len=1;//一定要注意不连续后len要变回1啊！
		}
	}
	if(maxv!=-1)cout<<maxv<<endl;
	else puts("No");
	
	return 0;
}

题解：B4277 [蓝桥杯青少年组国赛 2023] 主要成分

文章操作

前言

正言

代码

80分

100分

相关推荐

评论

题解：B4277 [蓝桥杯青少年组国赛 2023] 主要成分