TIOJ-1861

2qbingxuan

2020-05-01

TIOJ , greedy

蘿莉切割問題

https://tioj.ck.tp.edu.tw/problems/1861

Description

請你把一個數字$L$切成$a_1, a_2, \dots, a_n$
切一個數字$x$的代價是$x$，可以把它切成$b, x-b$兩個數字
找出最小的代價

Solution

霍夫曼編碼XD老題目
把切割的過程看成一個二元樹，每個$a_i$都代表一個葉子
其餘的節點代表合併中會出現的數字(?)
那麼總代價就是所有葉子的權重乘上各自的深度的和
我們想要讓這個代價越小越好
可以發現，在最優解$T$中：

沒有節點只有一個兒子，只要不是葉子的節點都恰好有兩個子節點
深度最大的那層節點一定是權重最小的，否則可以直接交換得到更優解

由上面兩點可以發現，權重最小的兩個節點一定都在最深的那一層
並且可以在不影響代價的情況下交換節點使得最小的兩個節點互為兄弟
結論是：每次把最小和次小的節點合併成一個節點，一定可以得到最佳解

(QQ我覺得我不會查也不會寫證明)

要怎麼維護所有節點的最小和次小呢？用一個heap就可以啦

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 100025;
#define int ll
int v[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n,ans;
    while(cin >> n) {
        ans = 0;
        for(int i = 0; i < n; i++) cin >> v[i];
        std::priority_queue<int,vector<int>,greater<int>> pq(v,v+n);
        while(pq.size() > 1) {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            ans += (x+y);
            pq.push(x+y);
        }
        cout << ans << '\n';
    }
}