————ACM训练————|POJ 3253 fence Repair 一个很有趣的贪心解法
Fence Repair
农夫约翰为了修理栅栏，要将一块很长的木板切割成 N 块，准备切成的木板长度为 Ln ，未切割前木板的长度恰好为切割后木板长度的总和。每次切断木板时，需要的开销为这块木板的长度。例如长度为21的木板要切成长度为 5、8、8 的三块木板，长 21 的木板切成长度为 13 和 8 的木板时 开销为 21 。再将长度为13的板切成长度为 5 和 8 的板时，开销为 13 。于是合计开销为 34 。 请求出按照目标要求将木板切割完的最小开销是多少。
题目中 1 <= N <= 20000 ， 0 <= Li <= 50000
输入：第一行是将木板切割成的块数 N ，第二行有 N 个数，分别为第 Li 块木板的长度。
输出：k，木板切割完的最小开销。
sample input:
3
8 5 8
sample output:
34
第一次做的时候感觉可以用贪心做，但是木板的切割顺序不确定，自由度很高，参考了书本的解法，
其实可以用略微奇特的贪心算法求解。
首先，切割的方法可以使用二叉树来描述。
文章图片
这里每一个叶子节点就对应了切割出的一块块木板，叶子节点的深度就对应了 为了得到对应木板所需要的切割次数，开销的合计就是各个叶子节点的 木板的长度*节点的深度 的总和。例如上图的实例就可以这样计算：
3*2+4*2+5*2+1*3+2*3=33
此时的最佳切割方法首先应该具有以下性质：
最短的板与次短的板的节点应当是兄弟节点
罪域最优解来讲，最短的板应当是深度最大的叶子节点之一。所以与这个叶子节点同一深度兄弟节点一定存在，并且由于同样是最深的叶子节点，所以应该对应于次短的板。
【————ACM训练————|POJ 3253 fence Repair 一个很有趣的贪心解法】不放将Li按照大小顺序排列，那么最短的板是 L1 ，次短的板是 L2 ，如果他们在二叉树中间是兄弟节点，就意味着他们是从一块长度为 L1+L2 的板切割得来的。由于切割顺序是自由的，不妨当做是最后被切割。这样一来，这次切割之前就有 L1+L2，L3，L4,...,Ln 这样的 N-1 块木板存在。递归地将这 N-1 块木板的问题求解，就可以求出整个问题的答案。
#include
#include
#include
#include int N,L[50050];
long long ans;
using namespace std;
void solve()
{
ans=0;
while(N > 1)//直到木板计算到只有一块时为止
{
int mii1=0,mii2=1;
//求出最短的板mii1和次短的板mii2
if(L[mii1] > L[mii2]) swap(mii1,mii2);
for (int i=2;
i>N;
for (int i=0;
i 推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术