题目链接

题意：给出一个式子，但这个式子不一定是等式，在‘+’，‘-’，‘=’符号位置不变的情况下，又一次排列数字的位置，使其成为等式。假设能够的话。输出当中一种排列方式。

思路：我们将等号右边的数所有移动到等号右边，比如a+b-c=d-e,移动后变成a+b+e-(c+d)=0。也就是a+b+e=c+d。所以当式子能够变化成等式时，所有数的和必定是偶数。那么问题能够转化为在n个数中找出m个数（m的值为等号左边的整数的数量），使m个 数的和为从和的一半。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 1005;

char str[MAXN], Lsy[MAXN], Rsy[MAXN], vis[MAXN];

int arr[MAXN], front[MAXN], back[MAXN];

int cnt1, cnt2, eql, Lnum, ans, flag, L, R;

int init() {

    cnt1 = 1, cnt2 = eql = L = R = 0;

    int l = strlen(str), sum = 0;

    sscanf(str, "%d", &arr[0]);

    sum = arr[0];

    for (int i = 0; i < l; i++) {

        if (str[i] == '+' || str[i] == '-' || str[i] == '=') {

            if (str[i] == '=')

                eql = i;

            if (!eql) {

                Lsy[L] = str[i];

                L++;

            }

            else if (eql != i) {

                Rsy[R] = str[i];

                R++;

            }

            sscanf(str + i + 1, "%d", &arr[cnt1]);

            sum += arr[cnt1++];

        }

    }

    Lnum = 1;

    for (int i = 0; i < l; i++) {

        if (i < eql && str[i] == '+')

            Lnum++;

        else if (i > eql && str[i] == '-')

            Lnum++;

    }

    return sum;

}

int dfs(int k, int pos, int cur) {

    if (k == Lnum) {

        if (cur == ans)

            return true;

        return false;

    }

    if (Lnum - k > cnt1 - pos)

        return false;

    if (pos < cnt1 && cur + arr[pos] <= ans) {

        vis[pos] = 1;

        if (dfs(k + 1, pos + 1, cur + arr[pos]))

            return true;

        vis[pos] = 0;

    }

    if (pos < cnt1 && dfs(k, pos + 1, cur))

        return true;

    return false;

}

void outPut() {

    int x = 0, y = 0;

    for (int i = 0; i < cnt1; i++) {

        if (vis[i])

            front[x++] = arr[i];

        else

            back[y++] = arr[i];

    }

    printf("%d", front[--x]);

    for (int i = 0; i < L; i++) {

        printf(" %c ", Lsy[i]);

        if (Lsy[i] == '+')

            printf("%d", front[--x]);

        if (Lsy[i] == '-')

            printf("%d", back[--y]);

    }

    printf(" = ");

    printf("%d", back[--y]);

    for (int i = 0; i < R; i++) {

        printf(" %c ", Rsy[i]);

        if (Rsy[i] == '+')

            printf("%d", back[--y]);

        if (Rsy[i] == '-')

            printf("%d", front[--x]);

    }

    printf("\n");

}

int main() {

    while (gets(str)) {

        int s = init();

        if (s % 2)

            printf("no solution\n");

        else {

            ans = s / 2;

            memset(vis, 0, sizeof(vis));

            if (dfs(0, 0, 0))

                outPut();

            else

                printf("no solution\n");

        }

    }

    return 0;

}