【贪心+堆】锯木
【【贪心+堆】锯木】锯木(cut.c/cpp/pas)
【题目描述】
LazyChild需要将一根非常长的木棒切成n段，每段的长度分别为L1，L2，…，LN个长度单位。∑Li(I= 1，2，…，N)恰好就是原木棒的长度。我们认为切割时仅在整数点处切且没有木材损失。
LazyChild发现，每一次切割花费的体力与该木棒的长度成正比，不妨设切割长度为1的木棒花费1单位体力。
LazyChild想请你帮他计算出最少要多少体力。
【输入文件】
第一行一个整数n。
第二行n个整数，分别表示L1，L2，…，LN。
【输出文件】
一行一个整数表示，LazyChild要付出的最少体力值。
【样例输入】
4
3 5 7 11
【样例输出】
49
【数据规模和约定】
对于30%的数据，n <= 10
对于100%的数据，n <= 100000，Li<= 1000
【考察点】
贪心策略+数据结构
【思路】
换一个名字，这货叫做果子合并
【提交情况】
216了7组嘲讽我吧……
【经验】
骚年别冲动……开堆得时候空间记得*4
【收获】
考试千万不能激动……
ACCode：
Program cut;
Varn,size:longint;
heap:array[0..400010]of longint;
Procedure terminate;
beginclose(input);
close(output);
halt;
end;
Procedure insert(x:longint);
vari,c:longint;
begininc(size);
i:=size;
heap[size]:=x;
while (i>1)and(x>1])do beginc:=heap[i];
heap[i]:=heap[i>>1];
heap[i>>1]:=c;
i:=i>>1;
end;
end;
Procedure delete;
vari,j,x,c:longint;
beginheap[1]:=heap[size];
i:=1;
j:=2;
x:=heap[1];
dec(size);
if (heap[j]>heap[j+1]) then j:=j+1;
while (x>heap[j])and(j<=size) dobeginc:=heap[i];
heap[i]:=heap[j];
heap[j]:=c;
i:=j;
j:=i<<1;
if heap[j+1]推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长