最近问问上的高手呢????? 求注释喽
Description
输入由{'o','r','z'}组成的字符系列对其按字母顺序排序。
如果规定排序过程只能做交换工作来达到排序效果(类似冒泡排序)。
求最小交换次数。
Input
一个整数T,表示测试数据个数。
每个测试数据包含一个数字n(字符个数,不计空格),0<n<10000 和字符序列str。
Output
最小交换次数。
Sample Input
3 3 z ro 2 z r 5 o orr z
Sample Output
1 1 0
Hint
Hint:
字符序列
z,r,o
排完序后为
o,r,z
所以只要交换z,o
即1 次就能达到排序效果
#include<stdio.h>
int f(char t){return t=='o'?0:t=='r'?1:t=='z'?2:3;}
int m(int a,int b){return a<b?a:b;}
int main()
{
char a[10000],t;
int b[3][3],c[3],n,i,j,k;
gets(a);
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<3;i++)
for(j=0;j<3;j++)
b[i][j]=c[i]=0;
for(i=0;i<n;i++)
while((t=getchar()))
if(f(t)<3)
{
c[f(t)]++,a[i]=t;
break;
}
for(n=k=i=0;i<3;i++)
for(j=0;j<c[i];k++,j++)
b[i][f(a[k])]++;
for(n=i=0;i<3;i++)
{
j=(i+1)%3;
k=m(b[i][j],b[j][i]);
n+=k;
b[i][j]-=k;
b[j][i]-=k;
n+=(b[0][1]?b[0][1]:b[0][2])*2;
}
printf("%d\n",n);
}
return 0;
}