洛谷 Sorting a Three-Valued Sequence 三值的排序

Description

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

Input

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

Output

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

Sample Input

Sample Output

4

这个题以前做过一次，现在在巩固一下。

对于不在正确位置的数字，会有两种方式，一种是 “ 1 3 2 ”（有一个数字在正确位置），这样只需要交换一次即可，另一种是“ 3 1 2 ”（三个数字都不在正确的位置），这样需要交换两次。
如果全部的第一种方式已经修正完毕，那么剩下的就只有第二种方式了。

将线段划分成三个区间，然后将这三个区间抽象成三个点，转化为“ 1 2 3 ”这三个数的排列方式。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<string>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<stack>
  9 #include<deque>
 10 #include<map>
 11 #include<iostream>
 12 using namespace std;
 13 typedef long long  LL;
 14 const double pi=acos(-1.0);
 15 const double e=exp(1);
 16 const int N = 10009;
 17 
 18 struct num{
 19     int a;
 20     int b;
 21     int c;
 22 }num[4];
 23 int con[1009];
 24 int main()
 25 {
 26     int i,p,j,n;
 27     int a,b,c,aa,bb,cc;
 28     a=b=c=aa=bb=cc=0;
 29     memset(num,0,sizeof(num));
 30     scanf("%d",&n);
 31     for(i=1;i<=n;i++)
 32     {
 33         scanf("%d",&con[i]);
 34         if(con[i]==1)
 35             aa++;
 36         else if(con[i]==2)
 37             bb++;
 38         else
 39             cc++;
 40     }
 41     for(i=1;i<=aa;i++)
 42     {
 43         if(con[i]==1)
 44             num[1].a++;
 45         if(con[i]==2)
 46             num[1].b++;
 47         if(con[i]==3)
 48             num[1].c++;
 49     }
 50     for(i=aa+1;i<=aa+bb;i++)
 51     {
 52         if(con[i]==1)
 53             num[2].a++;
 54         if(con[i]==2)
 55             num[2].b++;
 56         if(con[i]==3)
 57             num[2].c++;
 58     }
 59     for(i=aa+bb+1;i<=n;i++)
 60     {
 61         if(con[i]==1)
 62             num[3].a++;
 63         if(con[i]==2)
 64             num[3].b++;
 65         if(con[i]==3)
 66             num[3].c++;
 67     }
 68 
 69 //    for(i=1;i<=3;i++)
 70 //        printf("%d %d %d
",num[i].a,num[i].b,num[i].c);
 71 
 72     int ans=0,mid;
 73 
 74     if(num[1].b!=0&&num[2].a!=0)
 75     {
 76         mid=min(num[1].b,num[2].a);
 77         ans+=mid;
 78         num[1].b-=mid;
 79         num[2].a-=mid;
 80     }
 81     if(num[1].c!=0&&num[3].a!=0)
 82     {
 83         mid=min(num[1].c,num[3].a);
 84         ans+=mid;
 85         num[1].c-=mid;
 86         num[3].a-=mid;
 87     }
 88     if(num[2].c!=0&&num[3].b!=0)
 89     {
 90         mid=min(num[2].c,num[3].b);
 91         ans+=mid;
 92         num[2].c-=mid;
 93         num[3].b-=mid;
 94     }
 95 
 96     ans+=(num[1].b+num[1].c+num[2].a+num[2].c+num[3].a+num[3].b)/3*2;
 97 
 98     printf("%d
",ans);
 99     return 0;
100 }

View Code