P7259（题解）

· · 题解

Part1 排序条件

条件实际上很容易得出：

就是 x , y 两个数都会多次出现。

1.假如 x 出现得多，最后就先输出 x（出现了多少次输出多少次）；反之，都懂的。

2.假如 x , y 出现的次数一样，就看谁出现的早，出现的早的那一位，先输出。

大概就是这样：


bool cmp(work x,work y){
    if(x.ans!=y.ans)return x.ans>y.ans;// ans记录的是分别出现的次数 
    else return x.ft<y.ft;// ft记录的是这个数出现出现在第几位 
}

Part2 储存

实际上这道题，想骗分的话，可以直接用桶（哈希）来储存某个数出现的次数。

毕竟数据范围……（对于100%的数据，1 \leqslant N \leqslant 10^3 1 \leqslant C \leqslant 10^9 1 \leqslant a_i \leqslant C)( 望而生畏）

所以直接定义一个大大的结构体呢：

struct work{
    int num;//储存这个数是好多
    int ans;//这个数出现了多少次
    int ft;//这个数是第几个出现的
}w[10005];

Part3 实现

Code：

#include<bits/stdc++.h>
using namespace std;
int n,c,cnt; 
int a[10005],b[10005];// a是这个数是多少，b是这个数是第几个出现的 
struct work{
    int num,ans,ft;// num记录这个数出现了多少次 
}w[10005];
bool cmp(work x,work y){
    if(x.ans!=y.ans)return x.ans>y.ans;// ans记录的是分别出现的次数 
    else return x.ft<y.ft;// ft记录的是这个数出现出现在第几位 
}
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        bool blog=0;// 标记 
        for(int j=1;j<i;j++){// 从前面出现了的数里面找相同的 
            if(a[i]==a[j]){
                blog=1;
                w[b[j]].ans++;// 这个数出现的次数++ 
                break;
            }
        }
        if(blog==0){// 标记为假，说明没有出现过这个数
            // 把它储存进去 
            w[++cnt].num=a[i];
            w[cnt].ans=1;
            w[cnt].ft=cnt;// 看它出现的是第几个 
            b[i]=cnt;// 在外面记录一次 
        }
    }
    sort(w+1,w+cnt+1,cmp);// 排序 

    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=w[i].ans;j++){
            cout<<w[i].num<<" ";
        }
    }
    return 0;
}