这题一开始我想成了逆序，然后写了之后才发现不对。于是就在想，后来我想到了下面的方法 首先求得1的个数k1和2的个数k2。然后我们对前k1个数进行操作，如果是排序好了的话，这前k1个数应该是1,如果是2的话，那么我们从第k2+1个数开始找1,找到第一个1后交换两个数(这样交换的次数是最少的)。如果是3的话，就从最后一个数往前找第一个1,然后交换两个数。同样这样交换的次数是最少的。对1操作完了之后，我们在对接下来的k2个数进行操作，如果不是2的话，就一定是3了，一定要交换。这样进行操作之后对后面的数就不用操作了，因为已经是排好序了的。 不过官方的我还没看贴下官方的报告吧
  官方报告
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)
好友链接
搜索
最新评论
阅读排行榜
评论排行榜
|
|