Archie

这只是一道橙题，为什么我要写呢，。

因为这个题可以用基数排序做

以下做法为基数排序+计数排序

计数排序

和桶排有所相似

首先，统计每个值的出现次数

然后呢，在值域范围内统计次数的前缀和

然后从后往前扫并统计

for(int i=m;i>=1;--i){
            b[tot[3][a[i]%10]--][3]=i;
        }

基数排序

​ 按照最小的关键字向最大的关键字排序。内部排序用计数排序实现就可以了

反正这个题值域非常小，所以只有三个关键字

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m;
int tot[4][101];
int x;
int a[2000006];
int b[2000006][4];
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&x);
        int cnt=1;
        a[i]=x;
        while(x){
            tot[4-cnt][x%10]++;
            x/=10;
            cnt++;
        }
        for(int i=cnt;i<=3;++i){
            tot[4-i][0]++;
        }
    }
        for(int i=1;i<=9;++i){
            tot[1][i]+=tot[1][i-1];
            tot[2][i]+=tot[2][i-1];
            tot[3][i]+=tot[3][i-1];
        }
        for(int i=m;i>=1;--i){
            b[tot[3][a[i]%10]--][3]=i;
        }   
        for(int i=m;i>=1;--i){
            b[tot[2][a[b[i][3]]/10%10]--][2]=b[i][3];
        }
        for(int i=m;i>=1;--i){
            b[tot[1][a[b[i][2]]/100%10]--][1]=b[i][2];
        }
        for(int i=1;i<=m;++i){
            cout<<a[b[i][1]]<<" ";
        }
    return 0;
}