T1

【题面】T678583 A美丽数 (beauty)

题目描述

小 B 对数字有着独到的见解，他认为一个数是美丽数当且仅当这个数的相邻两位都不相同。

例如12345、12121是美丽数，而123321、11不是美丽数。
现在小B想知道，对于所有满足以下条件的数中，最小的那个数是什么?如果不存在这样的美丽数，则输出-1。

· 对 于i(0≤i≤9), 这个数中是i 的位数一共有ai 个。

· 这个数不能有前导0,即012是不合法的。
有多组测试点，每组测试点现在给你a0～a9, 请你回答小B 的问题。

输入格式

第一行包含一个整数T。

接下来T 行，每行10个整数， a0～a9, 含义如题。

输出格式

输出T, 每行一个整数，表示答案。

输入输出样例 #1

输入 #1

12
6 0 0 0 0 0 0 0 0 5
0 1 0 2 0 0 0 0 0 0
3 0 0 0 2 0 0 1 0 0
0 1 2 3 4 5 6 7 8 9
1 2 0 1 5 0 1 0 0 0
2 1 1 0 1 5 0 0 0 0
6 0 1 0 2 0 0 0 1 0
8 1 0 0 1 0 0 0 0 0
5 2 0 0 2 0 1 0 0 0
3 0 0 0 0 3 0 2 1 1
3 1 0 5 0 0 1 0 0 0
0 1 2 0 0 1 0 1 0 5

输出 #1

-1
313
404070
123234345454565656767676787897979898989898989
1404143464
1505052545
-1
-1
1010404060
5050507879
1303030363
1929295979

说明/提示

对于100%的数据，保证：T≤10,1≤n,ai≤ 10⁵, 其中$n=∑ai（0≤i≤9）$

A: 保证最多只有2个ai>0。

B: 保证最多只有3个ai>0。

【代码】T678583 A美丽数 (beauty)

#include <bits/stdc++.h>
using namespace std;
int t,i,d,p,m,c,w,l,g,a[11],cnt[11],f;
string s;
bool j(int t,int b=-1){
    int mx=0;
    for(i=1;i<=10;i++){
        if(i-1==b) continue;
        if(cnt[i]>mx) mx=cnt[i];
    }
    return mx\*2<=t+1;
}
int main(){
    cin>>t;
    while(t--){
        for(i=1;i<=10;i++) cin>>a[i];
        m=c=0;l=-1;s="";
        for(i=1;i<=10;i++) m+=a[i];
        if(m==0){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) if(a[i]>c) c=a[i];
        if(c>(m+1)/2){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) cnt[i]=a[i];
        for(p=0;p<m;p++){
            f=0;
            for(d=1;d<=10;d++){
                g=d-1;
                if(cnt[d]==0) continue;
                if(g==l) continue;
                if(p==0&&g==0) continue;
                cnt[d]--;
                if(j(m-p-1,g)){
                    s+=char('0'+g);
                    l=g;
                    f=1;
                    break;
                }
                cnt[d]++;
            }
            if(!f){cout<<-1<<"\\n";break;}
        }
        if(f) cout<<s<<"\\n";
    }
}