• Each nodes has at most 2 children.
• Each node except the root has exactly one parent.
• There is exactly one root node. The root node does not have any parents.
• If a node has a left child, all values in the left subtree are less than or equal to the value of the value of the node itself.
• If a node has a right child, all values in the right subtree are strictly greater than the value of the node itself.

• The difference between sum of all values in the left subtree and sum of all values in the right subtree is minimum.
• If there is more than one way to minimize the difference, sum of all values in the left subtree is maximum.
• The right and left subtrees are also kuPellaKeS BST's.

The following rules describe a representation way for a BST:

• A BST with no subtrees is denoted by "value_of_root" (Quotes included for clarity).
• A BST which have only one subtree (Either left or right subtree), is denoted by "value_of_root(representation_of_subtree)" (Quotes included for clarity).
• A BST which have both of its subtrees, is denoted by "value_of_root(representation_of_left_subtree,representation_of_right_subtree)".

Input
The first line of input gives the number of cases, T. Then, T test cases follow. Each one starts with a line containing number of values 1<=n<=1000. Next line contains n integer numbers separated by a single space.

Output
For the xth test case, your program must output the line containing "Case #x:", followed by representation of the kuPellaKeS BST having the given numbers as node values.

Case #1: 7(5(3(2(1),4),6),9(8,10))
Case #2: 1(1(1(0(0))))
Case #3: -3(-4,-2(-1))

1st Amirkabir UT Annual Programming Contest  Final Round

題目描述：

建一棵二元樹, 符合左子樹皆小於等於它, 右子樹皆大於它。
建的時候要符合 KuPellaKeS BST 的設定, 左右子樹總和的差越小越好,
如果相同時, 則左子樹的總合越大越好。

題目解法：

很簡單地使用遞迴去解決, 呼叫前先排序一下數字。

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, A[1005], S[1005];
void dfs(int l, int r) {
    if(l > r)   return;
    int i;
    int mn = 0xfffffff, mx, idx = l;
    int left, right, diff;
    for(i = l; i <= r; i++) {//choose i parent
        if(i != r && A[i] == A[i+1])
            continue;
        left = S[i-1]-S[l-1];
        right = S[r]-S[i];
        diff = abs(right - left);
        if(diff < mn)
            mn = diff, mx = left, idx = i;
        if(left > mx && diff == mn)
            mx = left, idx = i;
    }
    printf("%d", A[idx]);
    if(l != r) {
        putchar('(');
        dfs(l, idx-1);
        if(idx != l && idx != r)
            putchar(',');
        dfs(idx+1, r);
        putchar(')');
    }
}
int main() {
    int testcase, cases = 0;
    int i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        sort(A+1, A+n+1);
        for(i = 1, S[0] = 0; i <= n; i++)
            S[i] = S[i-1] + A[i];
        printf("Case #%d: ", ++cases);
        dfs(1, n);
        puts("");
    }
    return 0;
}