[COCI2009-2010#3] SORT

_JF_ · 2023-01-16 21:29:16 · 题解

[COCI2009-2010#3] SORT

题目传送门

我们考虑记录一个数出现了多少次，但是由于值域太大，于是我们换一个方法，表示下标为 i 对应的这个数出现的次数为多少次，从当前这个数开始往后找，和它相等的话就加一，用 s_i 来表示。

如果一个数出现了多次，我们开一个值域大小的布尔型数组 vis 对这个数打标记。显然，按照第一段的统计方法，对于一个数来说，我从他第一次出现去统计所得的值，就是这个数在区间里面的数量就是正确的。如果后面有数和他相同，我们就不用统计了，不然会记录到其他的出现次数中去，会出错。

然后我们用 maxx 表示出现次数最多的次数，从后往前枚举出现次数，同时我们从前往后扫一遍 s 数组，如果当前的 s_i 等于这个出现次数，就输出对应的 a 数组中的值。

#include<bits/stdc++.h>
using namespace std;
const int N =1e9+10;
const int INF=1e6+10;
bool vis[N];
int a[INF],s[INF];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int maxx=-INT_MAX;
    for(int i=1;i<=n;i++)
    {
        if(vis[a[i]]==true)
            continue;
        vis[a[i]]=true;
        s[i]=1;
        for(int j=i+1;j<=n;j++)
            if(a[j]==a[i])
                s[i]++;
        maxx=max(maxx,s[i]);    
    } 
    for(int i=maxx;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
            if(s[j]==i)
            {
                for(int k=1;k<=i;k++)
                    cout<<a[j]<<" ";
            }
    }
    return 0;
}