Balanced Ternary String（贪心+思维）

题目大意：给一个字符串，这个字符串只由0,1,2构成，然后让替换字符，使得在替换字符次数最少的前提下，使新获得的字符串中0,1,2

　　　　　　这三个字符的数目相同，并且新获得的字符串的字典序要尽可能的小；

直接数组做法：暴力遍历

 /* */

 # include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int n;

 int c[];

 string s;

 int main()

 {

     ios_base::sync_with_stdio(false);

     cin>>n>>s;

     memset(c, , sizeof(c));

     for(int i=; i<n; i++ )

         c[s[i]-'']++;

     for(int i=; i<n&&c[]<n/; i++ )///0不够的时候从前往后换

     {

         if( c[s[i]-'']<=n/ )

             continue;

         if( s[i]!='' )///只要不是0,且多就换

         {

             c[s[i]-'']--;

             s[i] = '';

             c[s[i]-'']++;

         }

     }

     for(int i=n-; i>=&&c[]<n/; i-- )///2不够的时候从后往前换

     {

         if( c[s[i]-'']<=n/ )

             continue;

         if( s[i]!='' )///只要不是2,且多就换

         {

             c[s[i]-'']--;

             s[i] = '';

             c[s[i]-'']++;

         }

     }

     for(int i=; i<n&&c[]<n/; i++ )///1不够的时候,从前往后换

     {

         if(c[s[i]-'']<=n/ )

             continue;

         if( s[i]=='' )///先把多出来的2换了,不能换多的0,多的0要从后面换,否则字典序就大了

         {

             c[s[i]-'']--;

             s[i]='';

             c[s[i]-'']++;

         }

     }

     for(int i=n-; i>= && c[]<n/; i-- )///1还不够,从后往前换

     {

         if( c[s[i]-'']<=n/ )

             continue;

         if( s[i]!='' )///只要不是1,并且多就换

         {

             c[s[i]-'']--;

             s[i]='';

             c[s[i]-'']++;

         }

     }

     cout<<s<<endl;

     return ;

 }

用双向队列来做，跟数组做法一个思维，双向队列用来记录0,1,2的位置

 /* */

 # include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 deque<int>num[];

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     int n;

     cin>>n;

     string a;

     cin>>a;

     for(int i=; i<n; i++ )

         num[a[i]-''].push_back(i);///向队列位加入0,1,2的位置,num[0]记录0的位置,num[1]记录1的位置,num[2]记录2的位置

     int k=n/;

     if( num[].size()==num[].size() && num[].size()==num[].size())

         cout<<a<<endl;

     else

     {

         if( num[].size()>k )///2多,从前往后,先换成0,再换成1

         {

             while( num[].size()>k && num[].size()<k )

             {

                 int pos = num[].front();

                 num[].pop_front();

                 a[pos] = '';

                 num[].push_front(pos);

             }

             while( num[].size()>k && num[].size()<k )

             {

                 int pos = num[].front();

                 num[].pop_front();

                 a[pos] = '';

                 num[].push_front(pos);

             }

         }

         if( num[].size()>k )///1多,从前往后换成0,从后往前换成2

         {

             while( num[].size()>k && num[].size()<k )

             {

                 int pos = num[].back();

                 num[].pop_back();

                 a[pos] = '';

                 num[].push_back(pos);

             }

             while( num[].size()>k && num[].size()<k )

             {

                 int pos=num[].front();

                 num[].pop_front();

                 a[pos] = '';

                 num[].push_front(pos);

             }

         }

         if( num[].size()>k )///0多,从后往前先换成2,再换成1

         {

             while( num[].size()>k && num[].size()<k )

             {

                 int pos = num[].back();

                 num[].pop_back();

                 a[pos] = '';

                 num[].push_back(pos);

             }

             while( num[].size()>k && num[].size()<k )

             {

                 int pos = num[].back();

                 num[].pop_back();

                 a[pos] = '';

                 num[].push_back(pos);

             }

         }

         cout<<a<<endl;

     }

     return ;

 }

巴特西

Balanced Ternary String（贪心+思维）

最新文章

热门文章