题解 【CF1009B Minimum Ternary String】

Solution

首先明确题目要你干什么：原字符串经过任意转换后字典序最小的字符串，那么就是让小的尽量排在前面，观察可行的交换方式，发现只有 0 不能和 2 交换，也就是说，这两个数字之间的相对位置和顺序是固定的，那么只需要考虑数字 1 的位置，显然，1应当放在2的前面0的后面。这题就做完了。
但是如果你这样做，会 WA #6，为什么？因为这样子的话，如果你这字符串中没有 2，那么你的 1 就不会被输出来，特判一下就可通过。

Code

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

const int N = 1e5 + 9;

char ch[N],bt[N];
int len,p,flag;

int main() {
    scanf("%s",ch + 1); len = strlen(ch + 1);
    for(int i = 1;i <= len;i++) {
        if(ch[i] == '0' || ch[i] == '2') {
            bt[++p] = ch[i];
        }
    }
    for(int i = 1;i <= p;i++) {
        if(bt[i] == '2' && !flag) {
            for(int j = 1;j <= len - p;j++) putchar('1');
            flag = 1;
        }
        putchar(bt[i]);
    }
    for(int i = 1;i <= len;i++) {
        if(ch[i] == '2') flag = 114514;
    }
    if(flag != 114514) for(int i = 1;i <= len - p;i++) putchar('1');
    return 0;
}