B. Minimum Ternary String (这个B有点狠)
You are given a ternary string (it is a string which consists only of characters '0', '1' and '2').
You can swap any two adjacent (consecutive) characters '0' and '1' (i.e. replace "01" with "10" or vice versa) or any two adjacent (consecutive) characters '1' and '2' (i.e. replace "12" with "21" or vice versa).
For example, for string "010210" we can perform the following moves:
Note than you cannot swap "02"→→"20" and vice versa. You cannot perform any other operations with the given string excluding described above.
You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).
Stringaais lexicographically less than stringbb(if stringsaaandbbhave the same length) if there exists some positionii(1≤i≤|a|1≤i≤|a|, where|s||s|is the length of the stringss) such that for everyj<ij<iholdsaj=bjaj=bj, andai<biai<bi.
The first line of the input contains the stringssconsisting only of characters '0', '1' and '2', its length is between11and105105(inclusive).
Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (possibly, zero).
100210
001120
11222121
11112222
20
20
这场CF abcd题 我就觉得B题最难
这个题目卡了我好久好久 ,全是写BUG
代码有点毒瘤
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 10; 4 const int INF = 0x3fffffff; 5 typedef long long LL; 6 string s; 7 int sum0[maxn], sum1[maxn], sum2[maxn], vis[maxn]; 8 vector<int>a; 9 int main() { 10 cin >> s; 11 if (s[0] == '0') sum0[1] = 1; 12 if (s[0] == '1') sum1[1] = 1; 13 if (s[0] == '2') sum2[1] = 1; 14 for (int i = 1 ; i < s.size() ; i++) { 15 if (s[i] == '0') sum0[i + 1] = sum0[i] + 1, sum1[i + 1] = sum1[i], sum2[i + 1] = sum2[i]; 16 if (s[i] == '1') sum1[i + 1] = sum1[i] + 1, sum0[i + 1] = sum0[i], sum2[i + 1] = sum2[i]; 17 if (s[i] == '2') sum2[i + 1] = sum2[i] + 1, sum0[i + 1] = sum0[i], sum1[i + 1] = sum1[i]; 18 } 19 int cnt = 0; 20 int len = s.size(); 21 for (int i = 0 ; i < len ; i++) { 22 if (s[i] == '2') { 23 for (int j = 0 ; j < sum0[i]; j++) a.push_back(0); 24 for (int j = 0 ; j < sum1[len] ; j++) a.push_back(1); 25 for (int j = i ; j < s.size(); j++) { 26 if (s[j] == '1') continue; 27 if (s[j] == '2') a.push_back(2); 28 if (s[j] == '0')a.push_back(0); 29 } 30 cnt = 1; 31 break; 32 } 33 } 34 if (cnt == 0) { 35 for (int i = 0 ; i < sum0[len] ; i++) printf("0"); 36 for (int i = 0 ; i < sum1[len] ; i++) printf("1"); 37 } else { 38 for (int i = 0 ; i < a.size() ; i++) printf("%d", a[i]); 39 } 40 return 0; 41 }优质内容筛选与推荐>>
长按二维码向我转账
受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。
已发送
发送中
微信扫一扫
关注该公众号