Solution Idea

50034. See-saw

參考解答

版本一

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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int cmp(const void *a, const void *b) {
    int *x = (int *) a;
    int *y = (int *) b;
    if (x < y)    return -1;
    if (x > y)    return 1;
    return 0;
}
 
#define MAXN 1024
#define iswap(x, y) {int t = x; x = y, y = t;}
int n, ndiv2, A[MAXN];
int used[MAXN], path[MAXN];
 
int dfs(int idx) {
    if (idx == n-1) {
        int lw = 0, rw = 0;
        for (int i = 0, j = 1; i < ndiv2; i++, j++)
            lw += j * path[i];
        for (int i = ndiv2, j = 1; i < idx; i++, j++)
            rw += j * path[i];
        if (lw == rw) {
            for (int i = ndiv2-1; i >= 0; i--)
                printf("%d ", path[i]);
            printf("_^_");
            for (int i = ndiv2; i < idx; i++)
                printf(" %d", path[i]);
            puts("");
            return 1;
        }
        return 0;
    }
    for (int i = 0; i < n; i++) {
        if (used[i])    continue;
        used[i] = 1;
        path[idx] = A[i];
        if (dfs(idx+1))
            return 1;
        used[i] = 0;
    }
    return 0;
}
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
 
        ndiv2 = n/2;
//        qsort(A, n, sizeof(int), cmp);
        memset(used, 0, sizeof(used));
        int ret = dfs(0);
        if (ret == 0)
            puts("N");
    }
    return 0;
}

版本二

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
65
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int cmp(const void *a, const void *b) {
    int *x = (int *) a;
    int *y = (int *) b;
    if (x < y)    return -1;
    if (x > y)    return 1;
    return 0;
}
 
#define MAXN 1024
#define iswap(x, y) {int t = x; x = y, y = t;}
int n, ndiv2, m, A[MAXN], B[MAXN];
int path[MAXN];
 
int dfs(int idx) {
    if (idx == n-1) {
        int lw = 0, rw = 0;
        for (int i = 0, j = 1; i < ndiv2; i++, j++)
            lw += j * path[i];
        for (int i = ndiv2, j = 1; i < idx; i++, j++)
            rw += j * path[i];
        if (lw == rw) {
            for (int i = ndiv2-1; i >= 0; i--)
                printf("%d ", path[i]);
            printf("_^_");
            for (int i = ndiv2; i < idx; i++)
                printf(" %d", path[i]);
            puts("");
            return 1;
        }
        return 0;
    }
    for (int i = 0; i < m; i++) {
        if (B[i] == 0)    continue;
        B[i]--;
        path[idx] = A[i];
        if (dfs(idx+1))
            return 1;
        B[i]++;
    }
    return 0;
}
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
 
        ndiv2 = n/2;
        qsort(A, n, sizeof(int), cmp);
        m = 0;
        for (int i = 0; i < n; ) {
            int cnt = 0, j = i;
            while (i < n && A[i] == A[j])
                i++, cnt++;
            A[m] = A[j], B[m] = cnt, m++;
        }
        int ret = dfs(0);
        if (ret == 0)
            puts("N");
    }
    return 0;
}

版本三

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int cmp(const void *a, const void *b) {
    int *x = (int *) a;
    int *y = (int *) b;
    if (x < y)    return -1;
    if (x > y)    return 1;
    return 0;
}
 
#define MAXN 1024
#define iswap(x, y) {int t = x; x = y, y = t;}
int n, ndiv2, A[MAXN];
int used[MAXN];
int LR[2][MAXN];
int possible(int lw, int rw, int lidx, int ridx) {
    int ll = n-1, rr = ridx+1;
    for (int i = n-1; i >= 0; i--) {
        if (used[i])    continue;
        if (lidx < n)
            lw += ll * A[i], ll--, lidx++;
        else
            rw += rr * A[i], rr++, ridx++;
    }
    return lw >= rw;
}
int seesaw(int lw, int rw, int lidx, int ridx, int spos) {
    if (lw == rw && lidx == ndiv2 && ridx == ndiv2) {
        for (int i = ndiv2-1; i >= 0; i--)
            printf("%d ", LR[0][i]);
        printf("_^_");
        for (int i = 0; i < ndiv2; i++)
            printf(" %d", LR[1][i]);
        puts("");
        return 1;
    }
    if (lw > rw) {
        iswap(lw, rw);
        iswap(lidx, ridx);
        spos = !spos;
    }
    if (lidx == ndiv2)
        return 0;
    if (!possible(lw, rw, lidx, ridx))
        return 0;
    for (int i = 0, prev = INT_MIN; i < n; i++) {
        if (used[i])    continue;
        if (A[i] == prev)
            continue;
        used[i] = 1;
        LR[spos][lidx] = A[i];
        if (seesaw(lw + (lidx+1) * A[i], rw, lidx+1, ridx, spos))
            return 1;
        used[i] = 0;
        prev = A[i];
    }
    return 0;
}
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
 
        ndiv2 = n/2;
        qsort(A, n, sizeof(int), cmp);
        memset(used, 0, sizeof(used));
        int ret = seesaw(0, 0, 0, 0, 0);
        if (ret == 0)
            puts("N");
    }
    return 0;
}

Discussion