AT_abc444_d 题解

· · 题解

罚时呜呜。

考虑先用桶 t 维护从低到高第 i 位（即，个位是第 1 位，十位是第 2 位，以此类推）有多少个 1。譬如说 n=3,a=\{2,5,4\}，则有 t_2 = 3,t_3 = 2。

那么可以视作由 t_{\max a} \dots t_2 \space{} t_1 组成的一个数字，由于数字是以 10 进制表示的而 t_i 很可能超过 10，于是我们得模拟高精过程处理进位。

注意一些实现上的小细节，具体见代码吧。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 5e5+5;
int n,a[N],t[N],b[N],cnt;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),t[1]++,t[a[i]+1]--;
    sort(a+1,a+n+1);
    for(int i=1;i<=a[n];i++)t[i]+=t[i-1];
    for(cnt=1;cnt<=a[n]||b[cnt];cnt++){
        if(cnt<=a[n])b[cnt]+=t[cnt];
        b[cnt+1]+=b[cnt]/10,b[cnt]%=10;
    }for(int i=cnt-1;i>=1;i--)cout<<b[i];cout<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！