[USACO2.1]三值的排序 Sorting a Three-Valued Sequence

题目描述

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

写一个程序计算出，给定的一个 $1,2,3$ 组成的数字序列，排成升序所需的最少交换次数

输入格式

第一行一个正整数 $n$，表示奖牌个数。
接下来 $n$ 行，每行一个 $[1,3]$ 内的整数，表示奖牌。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
9
2
2
1
3
3
3
2
3
1

样例输出 #1

1
4

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 1000$。

题解

题目解析

统计1,2,3的个数，那么排好序的一定是分为三个区间，那么当某数位置错误时，有以下几种情况：

1、一个数字1跑到了区间2，同时区间2中的一个数字2跑到了区间1

2、一个数字1跑到了区间3，同时区间3中的一个数字3跑到了区间1

3、一个数字2跑到了区间3，同时区间3中的一个数字3跑到了区间2

4、一个数字1跑到了区间2，同时区间2中的一个数字2跑到了区间3，区间3中的一个数字3跑到了区间1

5、一个数字1跑到了区间3，同时区间3中的一个数字3跑到了区间2，区间2中的一个数字2跑到了区间1

很明显，前三种需要交换一次，第四、五种需要交换两次，可以先贪心找前三种交换，再找还有几个数未归位，这时由于只会剩下第四、五种情况，三个数为一组，每组需交换两次，所以答案为：前三种交换次数+未归位的数的个数×三分之二

方法解释：找到它的原结果和目标结果，并作差：

原：2 3 1 1

目标：1 1 2 3

差：1 2 -1 -2

此时要交换两个数只需要对差进行改变，如将2和第一个1交换，2的差减1,1的差加1，就都变成0了，最后只需要把差全部变为0即可。

样例解释：

编号：1 2 3 4 5 6 7 8 9

原：2 2 1 3 3 3 2 3 1

目标：1 1 2 2 2 3 3 3 3

差：1 1 -1 1 1 0 -1 0 -2

前三种交换次数:

未归位的数的个数:

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;

int a[1010],cunt[5],b[6];
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i]; //把数据输入进去,很好懂
        cunt[a[i]]++;//把相应每个牌的个数统计一下
    }
    for(int i=1;i<=n;i++){//这里利用a[i]的空间滚动存了差数组
        if(i <= cunt[1]) a[i] = 1 - a[i];
        if(i > cunt[1] && i <= cunt[1] + cunt[2]) a[i] = 2 - a[i];
        if(i > cunt[1] + cunt[2]) a[i] = 3 - a[i];
        b[2+a[i]]++;//因为会出现-1 -2的情况,统一加了2
    }
    //0:-2  1:-1  3:1  4:2
    cout << min(b[3],b[1])+min(b[0],b[4])+2*(max(b[3],b[1])-min(b[3],b[1])+max(b[0],b[4])-min(b[0],b[4]))/3;
    return 0;
}

吐槽

估计这道题过几天又不会了= =,有点迷糊…