USACO 2.1.3 – Sorting A Three-Valued Sequence

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int N, n, cycles=0, swaps=0, m=0, wrong[3][3] = {{ 0} };

int main() {
	vector<int> array, sorted;
	freopen("sort3.in", "r", stdin), freopen("sort3.out", "w", stdout);
	scanf("%d", &n);
	while(n-- && (scanf("%d", &N)!=0)) array.push_back(N), sorted.push_back(N);

	sort(sorted.begin(), sorted.end());

	for (size_t i = 0; i < array.size(); i++)
		if (array[i] != sorted[i])
			wrong[array[i] - 1][sorted[i] - 1]++;

	for (int i = 0; i < 3; i++)
		for (int j = i + 1; j < 3; j++)
			m = min(wrong[i][j], wrong[j][i]), swaps += m, wrong[i][j] -= m, wrong[j][i] -= m;

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
				cycles += i==j ? 0 : wrong[i][j];

	printf("%d\n", swaps + cycles / 3 * 2);

	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: