问题标题: 酷町堂:2639

0
1
已解决
陈泉宏
陈泉宏
高级守护
高级守护
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

 


2
已采纳
李牧之
李牧之
新手光能
新手光能

这一题非常变态,(本蒟蒻的代码长达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
我要回答