题解 【CF1009B Minimum Ternary String】
TRZ_2007
2021-05-24 16:21:37
**[题解 【CF1009B Minimum Ternary String】](https://www.luogu.com.cn/problem/CF1009B)**
# Solution
首先明确题目要你干什么:**原字符串经过任意转换后字典序最小的字符串**,那么就是让小的尽量排在前面,观察可行的交换方式,发现只有 ``0`` 不能和 ``2`` 交换,也就是说,这两个数字之间的**相对位置和顺序**是固定的,那么只需要考虑数字 ``1`` 的位置,显然,``1``应当放在``2``的前面``0``的后面。这题就做完了。
但是如果你这样做,会 WA #6,为什么?因为这样子的话,如果你这字符串中没有 ``2``,那么你的 ``1`` 就不会被输出来,特判一下就可通过。
# Code
```cpp
#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;
}
```