Sorting a Three-Valued Sequence_usaco2.1.3

DESCRIPTION

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

PROGRAM NAME: sort3

INPUT FORMAT

Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

OUTPUT FORMAT

A single line containing the number of exchanges required

翻译

对于给定只含有1、２、３的序列作升序排序，求最小交换次数

题解

精神状态不佳，一开始冒出了匹配的翔法，后来被自己否定了
因为先知道了有序序列，所以统计一下发现需要交换的情况就有六种：

• 1,2
• 2,1
• 1,3
• 3,1
• 2,3
• 3,2

对于对称的两种情况可以通过互换解决，交换次数是较小那个
剩下的需要三个数交换以获得目标序列，所以累加求和
∵交换三个数字其实只要两次
∴ans=ans/3*2

不是很难哦

source code

/*
ID:wjp13241
PROG:sort3
LANG:C++
*/

#include <stdio.h>

using namespace std;

struct sit
{
    int x,y;
    bool operator==(sit &a)
    {
        return a.x==x&&a.y==y;
    }
};

int p[6],t[1001],st[4],num[4];

sit s[6]={{1,2},{2,1},{1,3},{3,1},{2,3},{3,2}};

int min(int x,int y)
{
    return x<y?x:y;
}

int main()
{
    freopen("sort3.in","r",stdin);
    freopen("sort3.out","w",stdout);

    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&t[i]);
        num[t[i]]++;
    }

    st[1]=1;
    st[2]=num[1]+1;
    st[3]=num[1]+num[2]+1;

    for (int k=1;k<=3;k++)
    {
        for (int i=st[k];i<=st[k]+num[k]-1;i++)
            if (t[i]!=k)
            {
                sit tmp=(sit){k,t[i]};
                for (int j=0;j<6;j++)
                    if (tmp==s[j])
                    {
                        p[j]++;
                        break;
                    }
            }
    }

    int ans=0,cnt=0;
    for (int i=0;i<5;i+=2)
    {
        int tmp=min(p[i],p[i+1]);
        ans+=tmp;
        p[i]+=p[i+1]-tmp*2;
        p[i+1]=0;
    }

    for (int i=0;i<=5;i++)
        cnt+=p[i]*2;

    printf("%d\n",ans+cnt/3);

    fclose(stdin);
    fclose(stdout);
    return 0;
}