洛谷P1334 瑞瑞的木板

传送门

题目背景

瑞瑞想要亲自修复在他的一个小牧场周围的围栏。

题目描述

他测量栅栏并发现他需要 nn 根木板，每根的长度为整数 l_il i
​
。于是，他买了一根足够长的木板，长度为所需的 nn 根木板的长度的总和，他决定将这根木板切成所需的 nn 根木板（瑞瑞在切割木板时不会产生木屑，不需考虑切割时损耗的长度)。

瑞瑞切割木板时使用的是一种特殊的方式，这种方式在将一根长度为 xx 的木板切为两根时，需要消耗 xx 个单位的能量。瑞瑞拥有无尽的能量，但现在提倡节约能量，所以作为榜样，他决定尽可能节约能量。显然，总共需要切割 (n-1)(n−1) 次，问题是，每次应该怎么切呢？请编程计算最少需要消耗的能量总和。

输入格式

输入的第一行是整数，表示所需木板的数量 nn。
第 2 到第 (n + 1)(n+1) 行，每行一个整数，第 (i + 1)(i+1) 行的整数 l_il i
​ 代表第 ii 根木板的长度 l_il i 。

输出格式

一个整数，表示最少需要消耗的能量总和。

输入输出样例

输入 #1复制
3
8
5
8
输出 #1复制
34

说明/提示

输入输出样例 1 解释
将长度为 2121 的木板，第一次切割为长度为 88 和长度为 1313 的，消耗 2121 个单位的能量，第二次将长度为 1313 的木板切割为长度为 55 和 88 的，消耗 1313 个单位的能量，共消耗 3434 个单位的能量，是消耗能量最小的方案。

数据规模与约定

对于 100%100% 的数据，保证 1\le n \le 2 \times 10^41≤n≤2×10
4
，1 \leq l_i \leq 5 \times 10^41≤l
i
​
≤5×10
4
。

上代码：

#include
#include
using namespace std;
long long n,tree[20002],d,ans;    //基本的变量，记住要用longlong(或int64)
inline void insert(int d) {        //向堆中插入d 
    tree[0]++;
    tree[tree[0]]=d;
    push_heap(tree+1,tree+tree[0]+1,greater<int>());//小根堆 
}
inline void pop() {                //跳出一个数 
    pop_heap(tree+1,tree+tree[0]+1,greater<int>());
    tree[0]--;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>d;            //输入并插入d 
        insert(d);
    }
    for(int i=0; i<n-1; i++) {    //两次跳出最小值后求出和再插入堆 
        int c1=tree[1];
        pop();
        int c2=tree[1];        //小根堆tree[1]表示最小数 
        pop();
        insert(c1+c2);
        ans+=c1+c2;            //将c1+c2累加到ans 
    }
    cout<<ans;        //输出ans 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31