Description

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌序的时候。 在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。 写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。

Input

Line 1: N (1 <= N <= 1000) Lines 2-N+1: 每行一个数字,共N行。(1..3)

Output

共一行,一个数字。表示排成升序所需的最少交换次数。

Sample Input

9
2
2
1
3
3
3
2
3
1

Sample Output

4
解题思路:把对方阵营自己的棋子和自己阵营对方的棋子相互交换,每次至少一步,不妨设为x次; 
第三方阵营有自己的棋子,自己的阵营有第二方的棋子,第二方阵营有第三方的棋子,至少需要两步得以交换,
不妨设为y次。 故最少的排序的步数为x+y/3*2

#include <stdio.h>

int a[1001];

int compare(int s1,int e1,int num1,int s2,int e2,int num2){
    int i,j,sum=0;
    for(i=s1,j=s2;i<s1+e1 && j<s2+e2;i++,j++){
        if(a[i]==num2 || a[j]==num1){
            if(a[j]!=num1){
                for(;j<s2+e2;j++)
                    if(a[j]==num1)
                        break;
            }
            else if(a[i]!=num2){
                for(;i<s1+e1;i++)
                    if(a[i]==num2)
                        break;
            }
            if(i==s1+e1 || j==s2+e2)
                break;
            a[i]^=a[j];
            a[j]^=a[i];
            a[i]^=a[j];
            sum++;
        }
    }
    return sum;
}

void solve(int n){
    int i,sum=0,count=0;
    int num[3]={0};
    for(i=0;i<n;i++)
        num[a[i]-1]++;
    sum+=compare(0,num[0],1,num[0],num[1],2);
    sum+=compare(num[0],num[1],2,num[0]+num[1],num[2],3);
    sum+=compare(0,num[0],1,num[0]+num[1],num[2],3);
    for(i=0;i<num[0];i++){
        if(a[i]!=1)
            count++;
    }
 for(;i<num[0]+num[1];i++){
  if(a[i]!=2)
   count++;
 }
 for(;i<n;i++){
  if(a[i]!=3)
   count++;
 }
    sum+=count/3*2;
    printf(“%d\n”,sum);
}
int main(){
    int n;
    while(scanf(“%d”,&n)!=EOF){
        int i;
        for(i=0;i<n;i++)
            scanf(“%d”,&a[i]);
        solve(n);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation