题解 CF1009B 【Minimum Ternary String】

· · 题解

只模拟可能是会超时的。

通过仔细地读题我们可以知道，0 和 1 可以交换，1 和 2 可以交换，而 0 和 2 不可以交换。

也就是说 1 可以交换到整个字符串中任何一个位置。

那么，我们可以把所有的 1 取出，只剩下由 0 和 2 组成的字符串。

由于 0 和 2 不能交换，且要得到字典序最小的字符串，我们要把所有的 1 放在第一个 2 前。

然后要记得特判一下没有 2 的字符串。


#include <bits/stdc++.h>

#define loop(i, to)  for (num i = 0; i < to; ++i)

using namespace std;

int n, cnt, pos;
string dat, ans;

int main() {
    cin >> dat;
    loop (i, dat.size()) {
        if (dat[i] == '1') {
            ++cnt;
            continue;
        }
        ans += dat[i];
    }
    pos = ans.size();
    loop (i, ans.size()) {
        if (ans[i] == '2') {
            pos = i;
            break;
        }
    }
    loop (j, cnt) {
        ans.insert(ans.begin() + pos, '1');
    }
    cout << ans << endl;
}

以上。