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

Wide_Master · 2025-04-02 13:00:48 · 题解

前言

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

正言

首先，要所含的化学成分超过一半，那我们是不是能开一个桶来储存，但是，因为输入最大达到了 2 \times 10^9，我们不能开一个数组来储存，所以我们用 map 来储存。

如果你这样子交上去的话，你只有 80 分，为什么呢？因为 map 时间复杂度太高了。

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

代码

80分

//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分

//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;
}