Posted on 2009-03-26 13:27
superman 阅读(122)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("sort3.in", "r", stdin);
8 freopen("sort3.out", "w", stdout);
9
10 int n, x[1000];
11 int c[10][10] = { 0 };
12 int t1 = 0, t2 = 0, t3 = 0;
13
14 cin >> n;
15 for (int i = 0; i < n; i++)
16 {
17 cin >> x[i];
18 if (x[i] == 1) t1 += 1;
19 if (x[i] == 2) t2 += 1;
20 if (x[i] == 3) t3 += 1;
21 }
22
23 for (int i = 0; i < t1; i++)
24 {
25 if (x[i] == 2) c[1][2] += 1;
26 if (x[i] == 3) c[1][3] += 1;
27 }
28 for (int i = t1; i < t1 + t2; i++)
29 {
30 if (x[i] == 1) c[2][1] += 1;
31 if (x[i] == 3) c[2][3] += 1;
32 }
33 for (int i = t1 + t2; i < n; i++)
34 {
35 if (x[i] == 1) c[3][1] += 1;
36 if (x[i] == 2) c[3][2] += 1;
37 }
38
39 int t, ans = 0;
40
41 t = min(c[1][2], c[2][1]);
42 c[1][2] -= t, c[2][1] -= t, ans += t;
43 t = min(c[1][3], c[2][1]);
44 c[1][3] -= t, c[2][1] -= t, c[2][3] += t, ans += t;
45
46 t = min(c[1][3], c[3][1]);
47 c[1][3] -= t, c[3][1] -= t, ans += t;
48 t = min(c[1][2], c[3][1]);
49 c[1][2] -= t, c[3][1] -= t, c[3][2] += t, ans += t;
50
51 t = min(c[2][3], c[3][2]);
52 c[2][3] -= t, c[3][2] -= t, ans += t;
53
54 cout << ans << endl;
55
56 return 0;
57 }
58