最小表达式

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给出一个包含数字1-9和加号的字符串，请你将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出那个最小表达式的值
合法的表达式的定义如下：

  • 一个数字，如233，是一个合法的表达式

  • A + B是合法的表达式，当且仅当 A , B 都是合法的表达式

保证给出的表达式经过重排，存在一个合法的解。

输入描述:
一行输入一个字符串，仅包含数字1-9和加号+。
字符串的长度小于5*10^5^。
输出描述:
一行输出一个数字，代表最小的解。
示例1
输入

111+1

输出

22

说明
11+11=22
示例2
输入

9998765432111

输出

1112345678999

示例3
输入

12+35

输出

38

说明
25+13 = 38

示例4
输入

23984692+238752+2+34+

输出

5461

题目大意

给你一个只有数字1到9的字符串，和若干个加号，让你输出加完之后最小值

解题思路

既然是让加完之后值最小，那么我们可以按照将这些数字从小到大排序，然后分成若干份，按照从小到大进行挑选就可以。因为加法运算最低位一定是在一起加，所以从最大的数字开始加，够一个块了就向前进一位还是手动模拟大法好然后按照大数加法进行计算就行。具体思路看代码吧，不得不说出题人的思路就是牛逼，%%%%%

代码

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long

string s;
ll a[20];
ll ans[500055];
int main()
{
    cin>>s;
    int sum=0,cut=1;
    for(char i:s)
    {
        if(i!='+') a[i-'0']++;//记录数字有几个 
        else cut++;//记录分几块，以为块数等于加号数+1 
    }
    int p=0;//记录分块 
    int q=0;//记录位数，模拟大数用 
    for(int i=9;i>0;i--)
    {
        while(a[i])//这里如果不明白，可以手动模拟下就行了 
        {
            ans[q]+=i;
            a[i]--;
            p=(p+1)%cut;//没p个数字一组，最高位先上排。 
            if(p==0) q++;
        }
    }
    for(int i=1;i<500050;i++)//模拟大数加法 
    {
        ans[i]=ans[i]+ans[i-1]/10;
        ans[i-1]=ans[i-1]%10;
    }
    int f=0;
    for(int i=500000;i>=0;i--) 
    {
        if(ans[i]){
            f=i;
            break;
        }
    }
    for(int i=f;i>=0;i--) cout<<ans[i];//输出 
    cout<<"\n";
    return 0;
}