# Solution Idea

## 參考解答

### 版本一

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#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;}


### 版本二

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#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;}