D|D - Balanced Ternary String （贪心） D-BalancedTernaryString（贪心）

题目链接：http://codeforces.com/contest/1102/problem/D

题目大意：给你一个字符串，这个字符串是由0,1,2构成的，然后让你替换字符，使得在替换的次数最少的前提下，使得新获得的字符串中0,1,2这三个字符的数目相同，并且新获得的字符串字典序要尽可能的小。

具体思路：我们先统计出每个字符的个数，想一下，除了三个都相等的情况下，这三个中的某一个肯定是大于n/3的，我们就枚举每一个字符。
【D|D - Balanced Ternary String （贪心）】如果是2多的话，我们就用1和0从前面进行替换。
如果是1多的话，我们就用2和0进行替换，为了保证字典序最小，我们将0从前面进行替换，2从后面进行替换，
如果是0多的话，我们就从后面开始替换，先从2开始，然后再从1开始。

AC代码：

1 #include 2 using namespace std; 3 const int maxn = 3e5+100; 4 int num[4]; 5 char str[maxn]; 6 int main() 7 { 8int len; 9scanf("%d",&len); 10scanf("%s",str); 11for(int i=0; itmp) 17{ 18for(int i=len-1; i>=0; i--) 19{ 20if(str[i]=='0') 21{ 22if(num[2]tmp) 23{ 24num[2]++,num[0]--,str[i]='2'; 25} 26else if(num[1]tmp) 27{ 28num[1]++,num[0]--,str[i]='1'; 29} 30} 31} 32} 33if(num[1]>tmp) 34{ 35for(int i=0; itmp) 40{ 41num[0]++,num[1]--,str[i]='0'; 42} 43} 44} 45for(int i=len-1; i>=0; i--) 46{ 47if(str[i]=='1') 48{ 49if(num[2]tmp) 50{ 51num[2]++; 52num[1]--; 53str[i]='2'; 54} 55} 56} 57} 58if(num[2]>tmp) 59{ 60for(int i=0; itmp) 65{ 66num[0]++; 67num[2]--; 68str[i]='0'; 69} 70else if(num[1]tmp) 71{ 72num[1]++; 73num[2]--; 74str[i]='1'; 75} 76} 77} 78} 79printf("%s\n",str); 80 } 81

转载于:https://www.cnblogs.com/letlifestop/p/10262737.html