题目大意：给一个字符串，这个字符串只由0,1,2构成，然后让替换字符，使得在替换字符次数最少的前提下，使新获得的字符串中0,1,2
这三个字符的数目相同，并且新获得的字符串的字典序要尽可能的小；
直接数组做法：暴力遍历
1 /* */ 2 # include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 6 int n; 7 int c[4]; 8 string s; 9 int main() 10 { 11 ios_base::sync_with_stdio(false); 12 cin>>n>>s; 13 memset(c, 0, sizeof(c)); 14 15 for(int i=0; i<n; i++ ) 16 c[s[i]-'0']++; 17 for(int i=0; i<n&&c[0]<n/3; i++ )///0不够的时候从前往后换 18 { 19 if( c[s[i]-'0']<=n/3 ) 20 continue; 21 if( s[i]!='0' )///只要不是0,且多就换 22 { 23 c[s[i]-'0']--; 24 s[i] = '0'; 25 c[s[i]-'0']++; 26 } 27 } 28 29 for(int i=n-1; i>=0&&c[2]<n/3; i-- )///2不够的时候从后往前换 30 { 31 if( c[s[i]-'0']<=n/3 ) 32 continue; 33 if( s[i]!='2' )///只要不是2,且多就换 34 { 35 c[s[i]-'0']--; 36 s[i] = '2'; 37 c[s[i]-'0']++; 38 } 39 } 40 41 for(int i=0; i<n&&c[1]<n/3; i++ )///1不够的时候,从前往后换 42 { 43 if(c[s[i]-'0']<=n/3 ) 44 continue; 45 if( s[i]=='2' )///先把多出来的2换了,不能换多的0,多的0要从后面换,否则字典序就大了 46 { 47 c[s[i]-'0']--; 48 s[i]='1'; 49 c[s[i]-'0']++; 50 } 51 } 52 53 for(int i=n-1; i>=0 && c[1]<n/3; i-- )///1还不够,从后往前换 54 { 55 if( c[s[i]-'0']<=n/3 ) 56 continue; 57 if( s[i]!='1' )///只要不是1,并且多就换 58 { 59 c[s[i]-'0']--; 60 s[i]='1'; 61 c[s[i]-'0']++; 62 } 63 } 64 cout<<s<<endl; 65 return 0; 66 }
用双向队列来做，跟数组做法一个思维，双向队列用来记录0,1,2的位置
1 /* */ 2 # include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 deque<int>num[3]; 6 7 int main() 8 { 9 ios::sync_with_stdio(false); 10 cin.tie(0); 11 cout.tie(0); 12 int n; 13 cin>>n; 14 string a; 15 cin>>a; 16 17 for(int i=0; i<n; i++ ) 18 num[a[i]-'0'].push_back(i);///向队列位加入0,1,2的位置,num[0]记录0的位置,num[1]记录1的位置,num[2]记录2的位置 19 int k=n/3; 20 if( num[0].size()==num[1].size() && num[1].size()==num[2].size()) 21 cout<<a<<endl; 22 else 23 { 24 if( num[2].size()>k )///2多,从前往后,先换成0,再换成1 25 { 26 while( num[2].size()>k && num[0].size()<k ) 27 { 28 int pos = num[2].front(); 29 num[2].pop_front(); 30 a[pos] = '0'; 31 num[0].push_front(pos); 32 } 33 while( num[2].size()>k && num[1].size()<k ) 34 { 35 int pos = num[2].front(); 36 num[2].pop_front(); 37 a[pos] = '1'; 38 num[1].push_front(pos); 39 } 40 } 41 42 if( num[1].size()>k )///1多,从前往后换成0,从后往前换成2 43 { 44 while( num[1].size()>k && num[2].size()<k ) 45 { 46 int pos = num[1].back(); 47 num[1].pop_back(); 48 a[pos] = '2'; 49 num[2].push_back(pos); 50 } 51 52 while( num[1].size()>k && num[0].size()<k ) 53 { 54 int pos=num[1].front(); 55 num[1].pop_front(); 56 a[pos] = '0'; 57 num[0].push_front(pos); 58 } 59 } 60 61 if( num[0].size()>k )///0多,从后往前先换成2,再换成1 62 { 63 while( num[0].size()>k && num[2].size()<k ) 64 { 65 int pos = num[0].back(); 66 num[0].pop_back(); 67 a[pos] = '2'; 68 num[2].push_back(pos); 69 } 70 71 while( num[0].size()>k && num[1].size()<k ) 72 { 73 int pos = num[0].back(); 74 num[0].pop_back(); 75 a[pos] = '1'; 76 num[1].push_back(pos); 77 } 78 } 79 cout<<a<<endl; 80 } 81 return 0; 82 }