Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

• 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;
}

您可能對以下文章有興趣

[UVA][窮舉] 129 - Krypton Factor

[UVA][SSSP] 523 - Minimum Transport Cost

[UVA][數學、N皇后單一快速解] 10094 - Place the Guards

[UVA][bfs] 10477 - The Hybrid Knight