loop


私信TA

用户名:uq_30093158753

访问量:797

签 名:

等  级
排  名 9877
经  验 671
参赛次数 0
文章发表 1
年  龄 20
在职情况 学生
学  校
专  业 软件工程

  自我简介:

解题思路:先引用一下  作者: 优雅的伊利 的解题思路:

因为只有只有3个字母(B,T,A),可以考虑暴力,分成三个区域A B C。
3个字母有6种排列方式。对于任意一种方式进行求解,然后取出最小值即可。
例如求解的顺序是BAT,我们要先得出要放B的位置上有多少个非B的数,然后这些位置肯定是和后面的AT交换的,但是和谁交换也是有要求的,A肯定要先和在A区间上的B交换,实在没有再放到T的区间上,然后再是A和T交换。总的来说,在B区间非B的数量与B区间交换完成后在A区间非A的数量和。


问题的关键在于想清楚 res = Abc + Bc + Ba - min(Ba,Ab)这个部分是怎么来的。将字符串分成三个部分ABC,计算ABC各部分的长度。下面重点来了!!!


A的非a部分是一定会交换到B和C上的(即Abc)。


在A区的b(Aa)和B区的a(Ba)交换时,A区的b的个数不一定够(Ab<Ba),怎么办?只能将A 区的c交换到B区,而这一部分最后还要再换回到C区的(Ba-Ab)。


A区的b(Aa)和B区的a(Ba)交换时,A区的b的个数够用甚至有余(Ab>=Ba),A区的b除了交换到B区,还会交换到C区,但这一部分b会再与B区的c交换时会回到B区,所以交换的次数是0(Ba-Ba)。


在A区非a交换完成后,B区c的个数就是交换前B区c的个数(Bc)和交换后多的c的个数Ba-min(Ab,Ba)。


所以最后每次循环交换的次数res = Abc + Bc + Ba - min(Ba,Ab)。


注意事项:

INF = 0x3f3f3f3f,一定要取得足够大。


参考代码:

#include<iostream>
#include<cstring>
using namespace std;
string s;
const int INF = 0x3f3f3f3f;
int func(string s,char A,char B,char C){
 int a=0,b=0,c=0;
 int Abc=0,Ab=0,Ba=0,Bc=0,res;
 int i,j;
 for(i=0;i<s.size();i++){
  if(s[i]==A)a++;
  if(s[i]==B)b++;
  if(s[i]==C)c++;
 }
 for(i=0;i<a;i++){
  if(s[i]!=A)Abc++;
  if(s[i]==B)Ab++;
 }
 for(i=a;i<a+b;i++){
  if(s[i]==A)Ba++;
  if(s[i]==C)Bc++;
 }
 res = Abc + Bc + Ba - min(Ba,Ab);
 return res;
}
int main(){
 while(cin>>s){
  int min=INF;
  int res; 
  char c[][4]={"BAT","ATB","TBA","BTA","ABT","TAB"};
  for(int i=0;i<6;i++){
   res=func(s,c[i][0],c[i][1],c[i][2]);
   if(res<min)min=res;
  }
  cout<<min<<endl;
 }
 return 0;
}


 

0.0分

8 人评分

  评论区

全排列容易超时
2021-05-15 07:32:49 | |
您好问一下这样的思路 咋错了 输入的字符串 TABTABBTTTT
先让他生成六个全排 AABBBTTTTTT    AATTTTTTBBB    BBBAATTTTTT   BBBTTTTTTAA   TTTTTTAABBB   TTTTTTBBBAA
比较字符不同的个数(偶数除2 奇数除2 加1 取最小值)
2020-11-12 13:29:26 | |
  • «
  • 1
  • »