這題一開(kāi)始我想成了逆序，然后寫(xiě)了之后才發(fā)現(xiàn)不對(duì)。于是就在想，后來(lái)我想到了下面的方法 首先求得1的個(gè)數(shù)k1和2的個(gè)數(shù)k2。然后我們對(duì)前k1個(gè)數(shù)進(jìn)行操作，如果是排序好了的話，這前k1個(gè)數(shù)應(yīng)該是1,如果是2的話，那么我們從第k2+1個(gè)數(shù)開(kāi)始找1,找到第一個(gè)1后交換兩個(gè)數(shù)(這樣交換的次數(shù)是最少的)。如果是3的話，就從最后一個(gè)數(shù)往前找第一個(gè)1,然后交換兩個(gè)數(shù)。同樣這樣交換的次數(shù)是最少的。對(duì)1操作完了之后，我們?cè)趯?duì)接下來(lái)的k2個(gè)數(shù)進(jìn)行操作，如果不是2的話，就一定是3了，一定要交換。這樣進(jìn)行操作之后對(duì)后面的數(shù)就不用操作了，因?yàn)橐呀?jīng)是排好序了的。 不過(guò)官方的我還沒(méi)看貼下官方的報(bào)告吧
  官方報(bào)告
1 We read the input into an array, and sort a copy of it in another array, so we know what we have and what we want.
2
3A swap touches two elements, so it can correct at most two misplaced elements. We run through the array looking for pairs of misplaced elements that a swap would correct, and do those swaps.
4
5The remaining misplaced elements form little cycles: a 1 where a 2 should be, a 2 where a 3 should be, and that 3 where the 1 should be. It takes two swaps to correct such a cycle. So we count the number of such cycles (by counting misplaced elements and dividing by three) and then add in two times that many swaps.
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10#include <assert.h>
11
12#define MAXN 1000
13
14int n;
15int have[MAXN];
16int want[MAXN];
17
18int
19intcmp(const void *a, const void *b)
20 {
21 return *(int*)a - *(int*)b;
22 }
23
24void
25main(void)
26{
27 int i, j, k, n, nn[4], nswap, nbad;
28 FILE *fin, *fout;
29
30 fin = fopen("sort3.in", "r");
31 fout = fopen("sort3.out", "w");
32 assert(fin != NULL && fout != NULL);
33
34 fscanf(fin, "%d", &n);
35
36  for(i=0; i<n; i++) {
37 fscanf(fin, "%d", &have[i]);
38 want[i] = have[i];
39 }
40 qsort(want, n, sizeof(want[0]), intcmp);
41
42 /**//* swaps that correct two elements */
43 nswap = 0;
44 for(i=0; i<n; i++)
45 for(j=0; j<n; j++) {
46 if(have[i] != want[i] && have[j] != want[j]
47 && have[i] == want[j] && have[j] == want[i]) {
48 have[i] = want[i];
49 have[j] = want[j];
50 nswap++;
51 }
52 }
53
54 /**//* remainder are pairs of swaps that correct three elements */
55 nbad = 0;
56 for(i=0; i<n; i++)
57 if(have[i] != want[i])
58 nbad++;
59
60 assert(nbad%3 == 0);
61 nswap += nbad/3 * 2;
62
63 fprintf(fout, "%d\n", nswap);
64 exit(0);
65}
66
67Dan Jasper from Germany writes:
68
69The previous solution needs a copy of the original list and O(N2) time. I think it was necessary with the original task, where you had to print out the exchange operations, but to just count them, there is a more efficient solution. You can count the "1", "2" and "3", so you can calculate in what parts (buckets) of the list they have to be. The rest of the solution is somehow equal to yours, but all in all it uses O(N) time and does not need a copy of the list.
70
71#include <stdio.h>
72
73int list[1000], N, res, count[3], start[3];
74in[3][3]; // this counts the number of "1"s in bucket "2",
75
76void readFile() {
77 FILE *f; int i;
78 f = fopen("sort3.in", "r");
79 fscanf(f, "%d", &N);
80 for(i = 0; i < N; i++) {
81 fscanf(f, "%d", &list[i]);
82 }
83 fclose(f);
84}
85
86void writeFile() {
87 FILE *f;
88 f = fopen("sort3.out", "w");
89 fprintf(f, "%d\n", res);
90 fclose(f);
91}
92
93void findBuckets() {
94 int i;
95 for(i = 0; i < N; i++) count[list[i]-1]++;
96 start[0] = 0;
97 start[1] = count[0];
98 start[2] = count[0] + count[1];
99}
100
101void findWhere() {
102 int i, j;
103 for(i = 0; i < 3; i++) {
104 for(j = 0; j < count[i]; j++) in[list[start[i] + j]-1][i]++;
105 }
106 }
107
108void sort() {
109 int h;
110 // 1 <-> 2
111 h = in[0][1];
112 if(in[1][0] < h) h = in[1][0];
113 res += h; in[0][1] -= h; in[1][0] -= h;
114 // 3 <-> 2
115 h = in[2][1];
116 if(in[1][2] < h) h = in[1][2];
117 res += h; in[2][1] -= h; in[1][2] -= h;
118 // 1 <-> 3
119 h = in[0][2];
120 if(in[2][0] < h) h = in[2][0];
121 res += h; in[0][2] -= h; in[2][0] -= h;
122
123 // Cycles
124 res += (in[0][1] + in[0][2]) * 2;
125}
126
127void process() {
128 findBuckets();
129 findWhere();
130 sort();
131}
132
133int main () {
134 readFile();
135 process();
136 writeFile();
137 return 0;
138}
139
140Bulgaria's Evgeni Dzhelyov writes:
141
142I read the elements one by one and count them, so we know exactly how 1s, 2s and 3s we have and we know how the sorted array looks like. Then I count the 2s in 1 and 1s in 2, so it is obvious that we need min(2sin1, 1sin2) swaps, I do the same for 1-3 and 2-3. The sum of all these mins give us the number of direct swaps we need. After that number of swaps we would have N 1s, 2s and 3s and we would need 2*N swaps, where N is max(2sin1, 1sin2) - min(2sin1, 1sin2).
143
144Here is the source code:
145
146#include <fstream>
147
148using namespace std;
149
150int min (int a, int b) { return a < b ? a : b; }
151int max (int a, int b) { return a > b ? a : b; }
152
153int main () {
154 int s[1024];
155 int n;
156 int sc[4] = {0};
157
158 ifstream fin("sort3.in");
159 ofstream fout("sort3.out");
160 fin>>n;
161 for (int i = 0; i < n; i++) {
162 fin>>s[i];
163 sc[s[i]]++;
164 }
165 int s12 = 0, s13 = 0, s21 = 0, s31 = 0, s23 = 0, s32 = 0;
166 for (int i = 0; i < sc[1]; i++){
167 if (s[i] == 2) s12++;
168 if (s[i] == 3) s13++;
169 }
170
171 for (int i = sc[1]; i < sc[1]+sc[2]; i++){
172 if (s[i] == 1) s21++;
173 if (s[i] == 3) s23++;
174 }
175
176 for (int i = sc[1]+sc[2]; i < sc[1]+sc[2]+sc[3]; i++){
177 if (s[i] == 1) s31++;
178 if (s[i] == 2) s32++;
179 }
180
181 fout<<min(s12, s21)+min(s13, s31)+min(s23, s32) +
182 2*(max(s12, s21) - min(s12, s21))<<endl;
183 return 0;
184}
185
186
|
|
常用鏈接
留言簿(1)
隨筆分類(99)
隨筆檔案(71)
好友鏈接
搜索
最新評(píng)論
閱讀排行榜
評(píng)論排行榜
|
|