0
已解决
2639 三值排序
题目描述 Description
现在有一个由N个整数组成的序列,每个整数都是整数A,B,C中的某一个,所以序列中只有这三种整数。
现在给你这样的一个序列,请问最少要交换多少个数的位置,才能将它们排成升序。
输入描述 Input Description
第一行,一个整数,N
接下来N行,每行一个整数
输出描述 Output Description
最少需要交换的次数
样例输入 Sample Input
9
2
2
1
3
3
3
2
3
1
样例输出 Sample Output
4
3
已采纳
这一题非常变态,(本蒟蒻的代码长达79行)
首先,在输入时把ABC三个数存起来,还要存他们的个数。
然后,应为只有三个数,所以最后的序列应该为
(假设A最小,B第二,C最大,且各有三个)
AAABBBCCC
可以发现,每个数都有自己对应的区间,利用个数算出他们各自区间的头和尾。
然后双重循环判断
第一重是固定的,循环两次,分别表示这次排序的区间(最小数是第一区间,然后是第二和第三)(第三不用判断,道理你肯定懂。)
第二重从1到n,把读入的数组遍历一遍,然后判断,如果这个数在上面循环的那个数的区间里,但并不是那个数,就继续判断
如果这个数等于第二个数,就先遍历第二区间,如果有第一区间的数,就交换,如果没有,就再遍历第三区间。
如果这个数等于第三个数,同上,但是先遍历第三区间,再遍历第二区间。
每交换一次ans++;
核心代码如下
for(int x=1;x<=2;x++){
for(int i=1;i<=N;i++){
if (a[i]!=n[x].num&&i>=n[x].st&&i<=n[x].end){
if (a[i]==n[x+1].num){
int f=0;
for(int j=n[x+1].st;j<=n[x+1].end;j++){
if (a[j]==n[x].num){
swap(a[i],a[j]);
ans++;
f=1;
break;
}
}
if (f==0&&x==1){
for(int j=n[x+2].st;j<=n[x+2].end;j++){
if (a[j]==n[x].num){
swap(a[i],a[j]);
ans++;
break;
}
}
}
}
else{
******(代码被和谐了,与上面一样,但是先遍历第三区间)
}
}
}
}
0
0
0
0