青岛公司网站建设/站长工具网

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

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

具体思路： 我们先统计出每个字符的个数，想一下，除了三个都相等的情况下，这三个中的某一个肯定是大于n/3的，我们就枚举每一个字符。

如果是2多的话，我们就用1和0从前面进行替换。

如果是1多的话，我们就用2和0进行替换，为了保证字典序最小，我们将0从前面进行替换，2从后面进行替换，

如果是0多的话，我们就从后面开始替换，先从2开始，然后再从1开始。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+100;
int num[4];
char str[maxn];
int main()
{int len;scanf("%d",&len);scanf("%s",str);for(int i=0; i<len; i++){num[str[i]-'0']++;}int tmp=len/3;if(num[0]>tmp){for(int i=len-1; i>=0; i--){if(str[i]=='0'){if(num[2]<tmp&&num[0]>tmp){num[2]++,num[0]--,str[i]='2';}else if(num[1]<tmp&&num[0]>tmp){num[1]++,num[0]--,str[i]='1';}}}}if(num[1]>tmp){for(int i=0; i<len; i++){if(str[i]=='1'){if(num[0]<tmp&&num[1]>tmp){num[0]++,num[1]--,str[i]='0';}}}for(int i=len-1; i>=0; i--){if(str[i]=='1'){if(num[2]<tmp&&num[1]>tmp){num[2]++;num[1]--;str[i]='2';}}}}if(num[2]>tmp){for(int i=0; i<len; i++){if(str[i]=='2'){if(num[0]<tmp&&num[2]>tmp){num[0]++;num[2]--;str[i]='0';}else if(num[1]<tmp&&num[2]>tmp){num[1]++;num[2]--;str[i]='1';}}}}printf("%s\n",str);
}