题解 | #数字#

E题解： 首先发现n范围不超过45，也就是987654321，最多9位 然后看题，输出拆分出来的最大的数并且数字不重复 所以，为了保证最大，我们首先要确定位数

我是怎么考虑位数的呢，从前缀和的角度考虑，已知，最大化利用数字的情况一定是越低位越小，那么越高位才能越大。 从后往前看，假设输入一个x，我一定想让它被拆分成....321的形式 那么我就直接前缀和，1+2+3+...+9，获得s1~s9 然后对输入的x判断，如果x正好等于某个s，直接输出就行，否则，纪录“x最后大于的si是哪个i”，这其实代表了我们理论上的最高位数

怎么证明？ 假如输入x，大于s5小于s6，那么我们得到的基础数列是54321，这是我认为的最高位数 如果它不是最高位数呢，那就有六位数，你无论怎么排，最省也是1~6全用了，所以x必须大于等于s6，与已知矛盾

位数确定以后：如果，从低到高看，想省着用数字怎么办？XXXXX321，后面的数字越小，留给前面的数字就越大 如果可以保证这样的规律，那么就能保证在同位数下获得的数是最大的 但是x-si有时候会剩下一些数字，这个数字小于（i+1） 这些数字怎么办呢，贪 怎么贪，位数已经确定了，我们就从最高位开始加，但是必须考虑到数字不重复 无论如何，高位的8肯定比低位的8要大，所以我们优先让高位的数字最大 好的，如果知道最小是...321，最高是987...也就不难发现了 所以，我们令j=9，意图在于，每一轮都尽可能的让这个高位数变成j（一开始按前缀和得到的最小数列，所以最高位肯定不是9，次高位肯定也不是8...） 凑出来9以后，j--，i--看次高位，凑8，以此类推 如果n不够凑出来这一位的j了，就直接输出这一位加n 以后n就是0了，后面的数字照常输出就行

#include<iostream>
#include<stack>
using namespace std;
int s[10],a[10];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=9;i++)
    {
        a[i]=i;
        s[i]=s[i-1]+i;
    }
    int pos;
    for(int i=1;i<=9;i++)
    {
        if(n<s[i])
        {
            pos=i-1;
            break;
        }
        if(n==s[i])
        {
            for(int j=i;j>=1;j--)
                cout<<j;
            return 0;
        }
    }
    n-=s[pos];
    for(int i=pos,j=9;i>=1;i--,j--)
    {
        if(n>=j-a[i])
        {
            n-=(j-a[i]);
            cout<<j;
        }
        else if(n!=0)
        {
            cout<<a[i]+n;
            n=0;
        }
        else
        {
            cout<<a[i];
        }
    }
}

刚刚跟别人分享了一下思路，正打在电脑上了，发一个玩玩hh