USACO Section 2.1: Prob Sorting A Three-Valued Sequence
5482 ワード
欲張りは、まず二人を交換してから交換すればいい.それから3つの輪廻を交換し、3つの輪廻ごとに2回交換しなければならない.
1 /*
2 ID: yingzho1
3 LANG: C++
4 TASK: sort3
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16
17 using namespace std;
18
19 ifstream fin("sort3.in");
20 ofstream fout("sort3.out");
21
22 int N;
23
24 int main()
25 {
26 fin >> N;
27 vector<int> f(N), g(N);
28 for (int i = 0; i < N; i++) fin >> f[i];
29 g = f;
30 sort(g.begin(), g.end());
31 int acount = 0;
32 for (int i = 0; i < N-1; i++) {
33 for (int j = i+1; j < N; j++) {
34 if (f[j] != g[j] && f[i] == g[j] && f[j] == g[i]) {
35 swap(f[i], f[j]);
36 acount++;
37 }
38 }
39 }
40 int count2 = 0;
41 for (int i = 0; i < N; i++) {
42 if (f[i] != g[i]) count2++;
43 }
44 fout << acount + count2/3*2 << endl;
45
46 return 0;
47 }