问题 3913 --基于三的交换排序(完善程序)

3913: 基于三的交换排序(完善程序)★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 59  解决: 49
[提交][状态][命题人:]

题目描述

给定一个数列,只包含1,2,3,每次操作可以交换一对数列中元素,问最少交换几次使得数列从小到大有序
下列程序以O(n)的复杂度完成了这个任务,请完善程序
#include <bits/stdc++.h>
using namespace std;
int main() 
{
	int N;
	cin >> N;
	vector<int> a(N, 0);
	vector<int> count(3, 0);
	for (int i = 0; i < N; i++) 
	{
		cin >> a[i];
		______(1)_________;
	}
	vector<vector<int> > map(3, vector<int>(3, 0));
	for (int i = 0; i < N; i++) 
	{
		if (i < count[0]) 
			map[0][a[i] - 1]++;
		else if (i < ______(2)_______) 
			map[1][a[i] - 1]++;
		else 
			map[2][a[i] - 1]++;
	}
	int ans = 0;
	int diff = ______(3)________;
	ans += diff;
	map[0][1] -= diff;
	map[1][0] -= diff;
	diff = min(map[0][2], map[2][0]);
	ans += diff;
	map[0][2] -= diff;
	map[2][0] -= diff;
	diff = min(map[1][2], map[2][1]);
	ans += diff;
	map[1][2] -= diff;
	map[2][1] -= diff;
	diff = _______(4)_______;
	ans += _______(5)_______;
	cout << ans << endl;
	return 0;
}

输入

输出

样例输入
Copy
6
2 1 3 3 2 1
样例输出
Copy
3

提示

来源

[提交][状态]