Oracle Accepts: 571
Submissions: 2141
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
问题描述

曾经有一位国王，统治着一片未名之地。他膝下有三个女儿。

三个女儿中最年轻漂亮的当属Psyche。她的父亲不确定她未来的命运，于是他来到Delphi神庙求神谕。

神谕可以看作一个不含前导零的正整数n n n。

为了得到真正的预言，他可以将n n n的各个数位重新排列，并将其分成两个不含前导零的正整数。

请你帮助他求出这两个正整数最大的和。如果不存在这样的两个正整数，输出”Uncertain”.

输入描述

第一行一个整数T T T (1≤T≤10) (1 \le T \le 10) (1≤T≤10)，代表数据组数。

接下来T T T行，每行一个正整数n n n (1≤n<1010000000) (1 \le n < 10 ^ {10000000}) (1≤n<10​10000000​​)。

输出描述

对于每组数据，输出一个整数表示最大的和。若不存在一种方案，输出”Uncertain”.

输入样例

3
112
233
1

输出样例

22
35
Uncertain

Hint

对于第一组数据，最优方案是将112 112 112分成21 21 21和1 1 1，最大的和为21+1=22 21 + 1 = 22 21+1=22。

对于第二组数据，最优方案是将233 233 233分成2 2 2和33 33 33，最大的和为2+33=35 2 + 33 = 35 2+33=35。

对于第三组数据，显然无法将一个数位分成两部分。

建议使用效率较高的读入方式。
题不难莫名写挂了。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int T,n;
const int maxn = 10000010;
int vis[10];
int a[maxn];
int b;
int len;
int mark;
void read()
{
    char c = getchar();
    while(c<'0'&&c>'9')c=getchar();
    while(c>='0'&& c<='9')
    {
    // a[++len]=c-'0';
        vis[c-'0']++;
        ++len;
        c = getchar();
    }
    mark = len - vis[0];
}
int main()
{
// freopen("1.in","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        len = 0;
// scanf("%d",&n);
// while(scanf("%1d",&num[++len]));
        scanf("\n");
        read();
        int lenth = len;
        if(mark<2)
        {
            printf("Uncertain\n");
            continue;
        }
        int pos = 0;
        bool flag=0;
        a[0]=0;
        for(int i=9;i>=0;i--)
        {   
            while(vis[i])
            {
                if(mark>1||flag)
                {
                    a[++pos] = i;
                    vis[i]--;
                    mark--;
                    len--;
                }
                else if(!flag) 
                {
                    b = i;
                    vis[i]--;
                    mark--;
                    len--;
                    flag=1;
                }
            }
            if(!len)break;
        }
        a[pos] += b;
        int now = pos;
        while(a[now]>9)
        {
            a[now]-=10;
            now--;
            a[now]++;
        }
        if(!a[0]&&!a[1])
        {
            printf("0\n");
            continue;
        }
        else if(a[0])printf("%d",a[0]);
        for(int i = 1;i<=pos;i++)printf("%d",a[i]);
        printf("\n");
    }
    return 0;
}