Codeforces-1009B B. Minimum Ternary String

You are given a ternary string (it is a string which consists only of characters ‘0‘, ‘1‘ and ‘2‘).

You can swap any two adjacent (consecutive) characters ‘0‘ and ‘1‘ (i.e. replace “01” with “10” or vice versa) or any two adjacent (consecutive) characters ‘1‘ and ‘2‘ (i.e. replace “12” with “21” or vice versa).

For example, for string “010210” we can perform the following moves:

  • 010210”  “100210“;
  • 010210”  “001210“;
  • 010210”  “010120“;
  • 010210”  “010201“.

Note than you cannot swap “02”  “20” and vice versa. You cannot perform any other operations with the given string excluding described above.

You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).

String aa is lexicographically less than string bb (if strings aa and bb have the same length) if there exists some position i (1i|a|, where |s| is the length of the string s) such that for every j<i holds aj=bj, and ai<bi.

题意:0,1,2组成的字符串,相邻的可以互换位置,01或者12可以互换,通过这些规则,求出原串能得到的最小字典序。

分析:就是一个分情况讨论的题,用冒泡强行模拟可能会超时,所以要总结规律。
可能的情况如下:

  1. 串中没有‘1’,因为0与1不可互换,所以原样输出
  2. 串中有0,1,或者1,2,没有第三个数,此时串可以任意交换,直接用sort得到最小字典序。
  3. 串中三者都有。那么采取以下策略,遇到先输出0(不要管1),1一定在0后面,但是0与2不能交换,所以以2作为隔断,遇到2的时候,输出所有的1(因为1作为中间交换值可以从后方挪到前面,所以这里输出全部)然后输出这个2.重复前面的策略到结束。

激动人心的代码实现:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int num_0,num_1,num_2;
int main()
{
  string str;
  cin>>str;
  for(int i=0;i<str.size();i++)
  {
    if(str.at(i)=='0') num_0++;
    else if(str.at(i)=='1') num_1++;
    else if(str.at(i)=='2') num_2++;
  }
  if(num_1==0) {cout<<str<<endl;return 0;}
  else if(num_0==0||num_2==0)
  {
    sort(str.begin(),str.end());
    cout<<str<<endl;
  }else
  {
    for(int i=0;i<str.length();i++)
    {
 			if(str.at(i)=='0') cout<<0;
      else if(str.at(i)=='2')
      {
        if(num_1!=0)
        {
          while(num_1!=0) {cout<<1;num_1--;}
          cout<<2;
        }else if(num_1==0) cout<<2;
      }
    }
  }
  return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

4 × 4 =