原题链接:http://codeforces.com/contest/1209/problem/C
题目大意:给你一组数,你给标号,只能标为1或2,然后将标号为1的拿出来放在标号为2的左边,能形成一个上升序列。
因为每个数都是0-9,所以枚举0-9作为分界点
#include <bits/stdc++.h>
using namespace std;
char s[300000];
int a[300000];
int b[300000];
int e[300000];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cin>>s;
int a1,b1,flag=0;
for(int k=0;k<10;k++)
{
int op,lpl=1;
a1=0;b1=0;
for(int i=0;i<n;i++)
{
op=(int)(s[i]-'0');
if(op>k)
{b[b1++]=op;
e[i]=2;}
if(op<k)
{a[a1++]=op;
e[i]=1;}
if(op==k)
{
if(b1==0)
{b[b1++]=op;
e[i]=2;
continue;}
if(op>=b[b1-1])
{b[b1++]=op;
e[i]=2;
continue;}
if(a1==0)
{a[a1++]=op;
e[i]=1;
continue;}
if(op>=a[a1-1])
{a[a1++]=op;
e[i]=1;
continue;}
if(op<b[b1-1]&&op<a[a1-1])
{lpl=0;
break;}
}
}
if(lpl==1)
{
int fa=1,fb=1,fc=0;
for(int i=0;i<a1-1;i++)
{
if(a[i]>a[i+1])
{fa=0;
break;}
}
for(int i=0;i<b1-1;i++)
{
if(b[i]>b[i+1])
{fb=0;
break;}
}
if(a1==0||b1==0)
{fc=1;}
if(a1>0&&b1>0){
if(a[a1-1]<=b[b1-1])
{fc=1;}}
if(fa==1&&fb==1&&fc==1)
{
flag=1;
for(int i=0;i<n;i++)
{cout<<e[i];}
cout<<endl;
break;
}
}
}
if(flag==0)
{cout<<"-"<<endl;}
}
}
123