B. Minimum Ternary String

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--B. Minimum Ternary String

题解

简单题。给定一个由0,1,2组成的三元序列,相邻位置的0,1/1,2可以交换位置。求可得到的字典序最小的字符串。
分析题意可知,0,2的相对位置无法改变,1可以移动至字符串内的任意位置。所以将第一个2前的0全移至字符串首部,将整个字符串中的1移动至首部的0后,之后的0,2输出顺序不变。

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
using namespace std;

string s;
int num0(0), num1(0);
bool pd(true);
int main() {
    cin >> s;
    for (auto i : s) {
        if (i == '1')num1++;
    }
    for (auto i : s) {
        if (i == '2'&&pd) {
            for (int j = 1; j <= num1; j++) {
                cout << '1';
            }
            pd = false;
        }
        if (i != '1')cout << i;
    }
    if (pd)
        for (int j = 1; j <= num1; j++) {
            cout << '1';
        }
}

标签: implementation, greedy

添加新评论