Uva11147 - KuPellaKeS BST

題目大意

KuPellaKeS BTS 是一種 BTS 但遵守以下規則：

1. 左子樹與右子樹的差要最小
2. 若左子樹與右子樹的差相同時，左子樹越大越優先
3. 左右子樹也都皆為 KuPellaKeS BTS

並將此樹以文字輸出，例:

1. node 5 底下有 3,6 這兩個 node 則表示為 5(3,6)
2. node 5 底下只有一個 node 3 表示為 5(3)
3. node 5 底下沒有任何子 node 表示為 5

重點觀念

分析

• 先將輸入進來的數列排序
• 再將每個 index 到前面的加總紀錄起來
• 先將 l,r 定為 0 與 n-1
• 用 dfs 跑出結果
  • 可以從區間的總和算出左右子樹加總出來的值
  • 若遇到重複的數字則跳過判斷

程式題目碼

#include <algorithm>
#include <iostream>

using namespace std;
#define N 1005
int node[N], sum[N];

void dfs(int l, int r) {
    if (l > r) {
        return;
    }

    int root = l, min_diff = INT32_MAX, max_left = INT32_MIN;

    for (int i = l; i <= r; i++) {
        if (i != r && node[i] == node[i + 1]) {
            continue;
        }
        int left = (i - 1 < 0 ? 0 : sum[i - 1]) - (l - 1 < 0 ? 0 : sum[l - 1]);
        int right = sum[r] - sum[i];
        int diff = abs(right - left);

        if (diff < min_diff) {
            root = i, min_diff = diff, max_left = left;
        }

        if (left > max_left && diff == min_diff) {
            root = i, max_left = left;
        }
    }

    cout << node[root];

    if (l != r) {
        cout << "(";

        dfs(l, root - 1);
        if (root != l && root != r) {
            cout << ",";
        }
        dfs(root + 1, r);
        cout << ")";
    }
}

int main() {
    int t;
    cin >> t;

    for (int i = 1; i <= t; i++) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> node[i];
        }

        sort(node, node + n);

        sum[0] = node[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + node[i];
        }

        cout << "Case #" << i << ": ";

        dfs(0, n - 1);

        cout << endl;
    }
    return 0;
}