http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1150
题意:任意多个ABC三个数,问最少交换多少个任意位置的两个数,能使字符窜有序
分析:记录ABC的个数,one two three,循环字符窜one的个数,若one中有B,则先从two中找是否含有A
若含有则交换,若没有则找three中的A。同理若one中有C,则先找three中的A,若three中没有A,则找
B中的A。
找完one后,就找two
当然这个很容易就能理解,当A中找到B,若在B中找到A,则ans最终+1,若B中没有A,则B和C中的A交换,
在接下来找的过程中,two中的C会和C中B交换,这样ans等同于+2
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1100;
char data[MN];
int len;
int swap_times;
void swap(int i,int k)
{
int tmp=data[i];
data[i]=data[k];
data[k]=tmp;
swap_times++;
}
bool find(char s,int start,int end,int k)
{
for(int i=start; i<end; i++)
{
if(s==data[i])
{
swap(i,k);
return true;
}
}
return false;
}
int main()
{
int T,i,j;
int one,two,three;
bool flag;
scanf("%d",&T);
while(T--)
{
swap_times=0;
scanf("%s",data);
len=strlen(data);
one=two=three=0;
for(i=0; data[i]; i++)
{
if(data[i]=='A') one++;
if(data[i]=='B') two++;
if(data[i]=='C') three++;
}
for(i=0; i<one; i++)
{
if(data[i]=='B')
{
flag=find('A',one,one+two,i);
if(!flag) find('A',one+two,one+two+three,i);
}
else if(data[i]=='C')
{
flag=find('A',one+two,one+two+three,i);
if(!flag) find('A',one,one+two,i);
}
}
for(i=one; i<one+two; i++)
{
if(data[i]=='C')
find('B',one+two,one+two+three,i);
}
printf("%d\n",swap_times);
}
return 0;
}