链接[https://vjudge.net/contest/413647#problem/C](http://www.nowcoder.com)

题意：给你n个数字的集合，划分成两个集合，让你确定每个数字在哪个集合，使得按原来顺序，集合1在集合2前面，能够构成单调不下降，输出任意解。
思路：
想了大概一小时吧，也是没想出来，原来的思路是尽量找小的变成1，然后从该位置往右扫把比它大的数都放在一起变成1，否则其他没被标记的都变成2，最后判断是否合理，后来想想这样得不对的，hack数据：5 25546 ，然后看了题解，我们把所有方案划分成划分为x，由于x比较小，把比x小的放在一边，比x大的放在另一边，如果碰到等于x的尽量放在右边，否则放左边，判断是否合法。
ac代码：

#include<iostream>
#include<cstring>
using namespace std;
int a[200010];
int col[200010];
int n;
bool check(int x)
{
    int lmax=-1,rmax=-1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<x)
        {
            if(a[i]<lmax)
                return 0;
            col[i]=1;
            lmax=a[i];
        }
        else if(a[i]==x)
        {
            if(a[i]>=rmax)
                rmax=a[i],col[i]=2;
            else 
                lmax=a[i],col[i]=1;

        }
        else
        {
            if(a[i]<rmax)
                return 0;
            col[i]=2;
            rmax=a[i];
        }
    }
    return 1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            scanf("%1d",&a[i]);
        bool ok = 0;
        for(int i=0;i<=9;i++)
            if(check(i))
            {
                ok=1;
                break;
            }
        if(ok)
        for(int i=1;i<=n;i++)
            cout<<col[i];
        else
            cout<<"-";
        cout<<endl;
    }
    return 0;
}