锐客网

  1. 首页 > it技术 > >

CF1102D-Balanced|CF1102D-Balanced Ternary String-（贪心）

http://codeforces.com/problemset/problem/1102/D
题意：
有n个字符，只能为012，现要通过变换让012的数量相等，并且使字典序最小。
解题：
【CF1102D-Balanced|CF1102D-Balanced Ternary String-（贪心）】由样例可以看出不能打乱原来的位置，按001122这样输出，只能一个一个替换，贪心。
1）只有0少了：优先把多余的2换成0，再把多余的1换成0。
2）只有1少了：优先把多余的2换成1，等0够了再把多余的0换成1。
3）只有2少了：等0和1够了，优先把多余的1换成2，再把多余的0换成2。
4）0和1都少了：2优先换成0，再换成1，再输出自己的。
5）0和2都少了：1优先换成0，1够了再换成2。
6）1和2都少了：0够了再把多余的0换成1，再换成2。
CF1102D-Balanced|CF1102D-Balanced Ternary String-（贪心）
文章图片
CF1102D-Balanced|CF1102D-Balanced Ternary String-（贪心）
文章图片

#include #include #include #include #include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; int n; string s; int main() { while(cin>>n) { cin>>s; int x=n/3; int zero=0,one=0,two=0; for(int i=0; i=0 && two>=0 ) { for(int i=0; i0 ) s[i]='0',zero++,two--; else if( s[i]=='1' && zero<0 && one>0 ) s[i]='0',zero++,one--; } } else if( one<0 && zero>=0 && two>=0 ) { int now0=0; for(int i=0; i0 ) s[i]='1',one++,two--; else if( s[i]=='0' && one<0 && zero>0 && now0==x ) s[i]='1',one++,zero--; } } else if( two<0 && zero>=0 && one>=0 ) { int now0=0,now1=0; for(int i=0; i0 && now1==x && two<0 ) s[i]='2',one--,two++; else if( s[i]=='0' && zero>0 && now0==x && two<0 ) s[i]='2',zero--,two++; } } else if( zero<0 && one<0 && two>0 ) { for(int i=0; i0 && zero<0 ) s[i]='0',two--,zero++; else if( s[i]=='2' && two>0 && one<0 ) s[i]='1',two--,one++; } else if( zero<0 && two<0 && one>0 ) { int now1=0; for(int i=0; i0 ) s[i]='0',zero++,one--; else if( s[i]=='1' && now1==x && two<0 && one>0 ) s[i]='2',two++,one--; } } else if( one<0 && two<0 && zero>0 ) { int now0=0; for(int i=0; i0 ) s[i]='1',one++,zero--; else if( s[i]=='0' && two<0 && now0==x && zero>0 ) s[i]='2',two++,zero--; } } cout
CF1102D
转载于:https://www.cnblogs.com/shoulinniao/p/11194296.html

    推荐阅读


    上一篇：codeforces|codeforces 1102D White Lines

    下一篇：我和烟叶的故事