UVa11147 - kuPellaKeS BST(遞迴)

題目大意

BST 是數的資料結構，kuPellaKeS BST 則是繼承 BST 後，還有以下特點

• kuPellaKeS BST 的左子樹、右子樹相差必須是最小的
• kuPellaKeS BST 如果有超過一種符合第一點的方法，則選擇左子樹權重最大
• 左右子樹也都必須符合 kuPellaKeS BST

並且我們 kuPellaKeS BST 也有特別的輸出方式

• 沒有左右子樹時，則輸出 root
• 只有左 or 右子樹時，則輸出 root(sub_node)
• 有左右子樹時，則輸出 root(left_sub_node, right_sub_node)

給你一數列，請輸出 kuPellaKeS BST
題目連結

重點觀念

• 建造 BST
• difference 在這邊是相減，並不是不一樣的意思

分析

difference 真的是太過分了，我一直被他誤導QQ。

• 我們可以明顯知道，建立一個 BST 不難，只需要一個遞迴就好，那我們現在的重點就是要讓 BST 變成 kuPellaKeS BST。
• 接下來我們就是根據此方式去實作，但是我們要怎麼找，才能符合題目的左右子樹切割條件呢？
  • 原本的 BST 是 (L+R)/2，有一個很明顯的公式。
  • n 最大只有 2000，那我們可以用暴力的方式解解看。
  • 畢竟 n 不大，2000 最多就 2 的 11 次，因此最壞情況下迴圈長度為 22000。
  • 用迴圈不斷去比較，找出符合題目要求的切割左右子樹方法。
• 一個小技巧，\(O(1)\)算出左右子樹大小
  • 可以使用區間查詢。
  • 先將數列進行排序
  • 也就是說，如果我們有一個陣列為 sum[i] = sum[i-1] + num[i]，新的 index 值會繼承救的數值並且加上當前數列數字
  • BST 的特性，左子樹的所有數值一定比 root 小，因此我們要查詢的區間就是 sum[root-1] - sum[L-1]，記住 root 並不是左子樹的範圍內、L 則在左子樹的範圍內
  • 反之，右子樹就是我們要查詢的區間就是 sum[R] - sum[root])
• 判斷輸出格式
  • 考慮左右子樹都有數值，就需要輸出逗號。
  • 因此我們可以用 root != L && root != R，也就是說 root 並不在左邊界 or 右邊界上，就表示 root 下一定還有左右子樹

心得

好久沒有寫演算法，腦袋變差很多QQ。 希望可以趕快恢復

參考連結

Uva11147 - KuPellaKeS BST by txya900619

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 2000
using namespace std;
int sum[MAXN], num[MAXN];
int t, n, kase=0;

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 && num[i] == num[i+1]) continue;
        int left_tree = (i == 0 ? 0 : sum[i-1]) - (L == 0 ? 0 : sum[L-1]); //左子樹總和
        int right_tree = sum[R] - sum[i]; //右子樹總和

        int diff = abs(right_tree - left_tree); //記住，需要 abs，不然樹會整個往左偏。
        int left = left_tree;
        if(diff < min_diff){
            root = i;
            min_diff = diff;
            max_left = left;
        }
        if(diff == min_diff && left > max_left){
            root = i;
            min_diff = diff;
            max_left = left;
        }
    }

    cout << num[root]; //輸出當前 root
    if(L != R ){
        cout << "(";
        dfs(L, root-1); //右子樹
        if(root != L && root != R) cout << ",";
        dfs(root+1, R); //左子樹
        cout << ")";
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++) cin >> num[i];
        sort(num, num+n);

        cout << "Case #" << ++kase << ": ";
        sum[0] = num[0];
        for(int i = 0; i < n; i++) sum[i] = sum[i-1] + num[i]; //計算區間總和
        dfs(0, n-1);
        cout << '\n';
    }
    return 0;
}