【题解】三色排序

题目描述
给定 n 个整数 a1,a2,…,an，每个数字都是 0,1,20,1,2 中的一个，请将其中的一部分数字两两交换，使得结果是升序的，请问最少需要几次交换？
输入格式
第一行：单个整数表示 n
第二行：nn 个整数表示a1,a2,…,an
输出格式
单个整数：表示最少交换次数。

数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤100,000；
对于 100% 的数据，1≤n≤1,000,000；
0≤ai≤2；
样例数据
输入:
5
2 0 1 2 0
输出:
1
说明:
将第一个2与最后一个0交换即可
【题解】
根据题目含义，可以分别统计0、1、2的数量，然后依据题目要求最少的交换，尽量保证在原有位置的数据不移动，因此统计，在前0个数字位置上出现了多少1和多少2，因为1和2是必须要换走的，同理统计在后2个数字位置上出现了多少1和0，因为1和0是必须要换走的，将这些数量相加并减掉重复部分，就是总共最少需要换走的元素数量。
实现代码

#include<bits/stdc++.h>
#include <iostream>　　　　 // cin  cout的头文件  基本输入流
#include <iomanip>　　　//cout输出时，保留小数fixed、setprecision的头文件 参数化输入／输出
#include <cstdio>　　　　//scanf、printf的头文件  定义输入／输出函数
#include <cmath>　　　　　//sqrt()求平方根、定义数学函数
#include <algorithm>　　　 //STL通用算法
#include <cstring>
#include <string>
const int N = 1e6+6;
int a[N],cnt[4]; 
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;	
	}
	int c=0,d=0,e=0,f=0;
	for(int i=1;i<=cnt[0];i++){
		if(a[i]==1){
			c++;
		}
		if(a[i]==2){
			d++;
		}
	}
	for(int i=n-cnt[2]+1;i<=n;i++){
		if(a[i]==0)
			e++;
		if(a[i]==1)
			f++;
	}
	int ans=c+d+e+f-min(d,e);
	cout<<ans<<endl;
	return 0;
}