50034. See-saw
難度：4.9/5
由Morris的解法3簡化而來，還不太懂原始程式碼possible()的剪枝的邏輯，想要modify成自己的理解也會TLE會WA。
Second Try: 5/5 Used Time 34:03 You need to sort the values from small to big first, I don't know why but sure...1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define swap(x, y) {int t = (x); (x) = (y); (y) = t;}
int n, div2;
int arr[20];
bool used[20];
int seesaw[2][10];
int cmp(const void* a, const void *b){
int num_a = *(int*)a;
int num_b = *(int*)b;
if(num_a > num_b) return 1;
else if(num_a < num_b) return -1;
else return 0;
}
static inline void print_seesaw(){
for(int i = div2 - 1; i >= 0; i--) printf("%d ", seesaw[0][i]);
printf("_^_");
for(int i = 0; i < div2; i++) printf(" %d", seesaw[1][i]);
printf("\n");
}
bool solve(int lw, int rw, int lidx, int ridx, int pos){
if(lidx == div2 && ridx == div2 && lw == rw){
print_seesaw();
return true;
}
if(lw > rw){
swap(lw, rw);
swap(lidx, ridx);
pos = !pos;
}
if(lidx == div2) return 0;
for(int i = 0; i < n; i++){
if(used[i] == true) continue;
used[i] = true;
seesaw[pos][lidx] = arr[i];
if(solve(lw + arr[i] * (lidx + 1), rw, lidx + 1, ridx, pos) == true){
return true;
}
used[i] = false;
}
return false;
}
int main(){
while(scanf("%d", &n) == 1){
for(int i = 0; i < n; i++){
scanf("%d", &arr[i]);
used[i] = false;
}
div2 = n / 2;
qsort(arr, n, sizeof(int), cmp);
if(solve(0, 0, 0, 0, 0) == false) printf("N\n");
}
}