欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

USACO 2.1.3 Sorting a Three-Valued Sequence

程序员文章站 2024-03-19 09:29:10
...

题目大意:

  这道题是说,给你一个长度为n的数组,然后,这个数组中只能包含1 2 3。求出将这个序列从小到大排序后的序列,所需要的最少的步数。

解题思路:

  这道题,拿到后,想到以前做过的一个bit求逆序数的题目,想了想,完全不搭边啊。于是,发现了,由于这个数组中只有1 2 3 这三个数字,所以,我们首先应该先对原数组进行一份copy。然后对copy后的数组从小到大进行排序。

与现在的数组的每一位进行比较,记录相同位置不同地方的所有可能情况。发现,在交换的时候,要么是两个两个进行交换,1<->2 2<->3 1<->3,要么是1->2,2->3 1->3,3->2,这样的交换,所以,我们可以一开始讲所有只交换一次的的交换

对都试一遍,然后,剩下来的就是要交换2次的情况了。

 

代码:

  

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

# include<cstdio>
# include<iostream>
# include<algorithm>
# include<fstream>

using namespace std;

# define MAX 1234

int a[MAX],b[MAX];
int change[MAX][MAX];

void print()
{
    for ( int i = 1;i <= 3;i++ )
    {
        for ( int j = 1;j <= 3;j++ )
            cout<<change[i][j]<<" ";
        cout<<endl;
    }
}

int main(void)
{
    //freopen("sort3.in","r",stdin);
    //freopen("sort3.out","w",stdout);
    int n; scanf("%d",&n);
    for ( int i = 0;i < n;i++ )
    {
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    sort(b,b+n);
    for ( int i = 0;i < n;i++ )
    {
        if ( a[i]!=b[i] )
        {
            change[a[i]][b[i]]++;
        }
    }
    print();
    int ans = 0;
    for ( int i = 1;i <= 3;i++ )
    {
        for ( int j = 1;j <= 3;j++ )
        {
            if ( change[i][j]&&change[j][i] )
            {
                int tmp = min(change[i][j],change[j][i]);
                ans+=tmp;
                change[i][j]-=tmp;
                change[j][i]-=tmp;
            }
        }
    }
    ans+=change[1][2]*2+change[2][1]*2;

    printf("%d\n",ans);

    return 0;
}