计蒜客 三值排序 贪心

题目连接

https://nanti.jisuanke.com/t/27

Description

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

写一个程序计算出,计算出的一个包括1、2、3三种值的数字序列,排成升序所需的最少交换次数。

Input

输入第1行为类别的数量N(1≤N≤1000)

输入第2行到第N+1行,每行包括一个数字(1或2或3)。

Output

输出包含一行,为排成升序所需的最少交换次数。

Sample Input

9
2
2
1
3
3
3
2
3
1

Sample Output

4

题意

最少交换多少次可以让3值按照升序排序?

题解

显然要用贪心解决。首先知道的是有三种方式交换是最优的:
1.1区中的2和2区中的1交换,一次能让两个数字到达正确位置。
2.1区中的3和3区中的2交换,同上。
3.2区中的3和3区中的2交换,同上。
本体显然有最优解结构,且交换次序不影响最优解结构,那么我们可以换一个角度看,先把1全部归位到1区,然后只要再令2中3和3中2回到正确位置即可,这个次数为max(2中3数目,3中2数目)。加上1归位的操作次数,便是贪心最优解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000+10;
int n,a[maxn],b[maxn];
int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(a,a+n);
int ans=0,tempx=0,tempy=0;
for(int i=0;i<n;++i){
if(a[i]==1 && b[i]!=1)
ans++;
if(a[i]==2 && b[i]==3)
tempx++;
if(a[i]==3 && b[i]==2)
tempy++;
}
ans+=max(tempx,tempy);
printf("%d\n",ans);
}