问题大意：农夫约翰为了修理栅栏，要将一块很长的木块切割成N块，准备切成的木板的长度为L1，L2...LN，未切割前的木板的长度恰好为切割后木板的长度的总和，每次切断木板的时候，需要的开销为这块木板的长度，例如长度为21的木板需要切成长度为5,8,8的三块木板，长为21的木板切成长为13和8的板时，开销为21,。再将长度为13的板切成长度为5和8的板时，开销是13，于是合计开销是34，然后要你求切割完的最小开销是什么。
乍眼看这一道题好像有很多种切割方案，似乎是很难解决的，但是我们这样想，就是当我们切一块木板的时候，我们所用的开销就是切割这一块木板所要用到的长度，我们得到了两块木板，这两块木板可以继续切的话，他们的总开销就是这两块木板的和，也就是一块长的木板。那么我们想到最后，就会发现其实就是我们得到了一个这样的东西，就是最小的板会所要用到的开销会占N次（视通过多少次分割得到这块板来定），如果我们要画一幅图来展示这个过程的话。。。
上面最大的开销是34=8*2+5*2+8（也就是二叉树的树叶对应节点大小乘以高度）
那么为了得到最小的开销，我们很容易就发现，我们只要把相对较小的节点放在比较深的地方就可以了，这是一种比较常用的贪婪的思想，证明我就省略了
那么现在我们只用不断地把最小的节点结合起来，最后就会形成最小的开销，那么不断找最小嘛，很容易就想到用堆，堆呢你可以自己写（熟练的话会很快），也可以直接用std（会比较简洁）
#include<stdio.h>
#include<stdlib.h> typedef int Position, *Heap; int Delete_Min(Heap, int *const);
void Push(Heap, int, int *const); int main(void)
{
int N, i, size = ;
int L1, L2, tmp;
long long ans = ; while (~scanf("%d",&N))
{
Heap pque = (Heap)malloc(sizeof(int)*N);
for (i = ; i < N; i++)
{
scanf("%d", &tmp);
Push(pque, tmp, &size);
}
while (size > )
{
L1 = Delete_Min(pque, &size);
L2 = Delete_Min(pque, &size); ans += (long long)L1 + L2;
Push(pque, L1 + L2, &size);
}
free(pque);
printf("%lld\n", ans);
}
} int Delete_Min(Heap heap,int *const size)
{
Position pr = , s1, s2, s;
int out = heap[], tmp = heap[(*size)--];
for (; pr <= *size;)
{
s1 = pr << ; s2 = s1 + ;
if (s2 <= *size)
{
if (heap[s1] < heap[s2]){ heap[pr] = heap[s1]; pr = s1; }
else{ heap[pr] = heap[s2]; pr = s2; }
}
else
{
if (s1 <= *size){ heap[pr] = heap[s1]; pr = s1;break; }
else break;
}
}
for (s = pr; s > ;)
{
if (s % == )
{
pr = s >> ;
if (heap[pr] > tmp) { heap[s] = heap[pr];s = pr;}
else break;
}
else
{
pr = (s - ) >> ;
if (heap[pr] > tmp){ heap[s] = heap[pr];s = pr; }
else break;
}
}
heap[s] = tmp;
return out;
} void Push(Heap heap, int item, int *const size)
{
Position s = ++(*size), pr;
for (; s > ;)
{
if (s % == )
{
pr = s >> ;
if (heap[pr] > item) { heap[s] = heap[pr]; s = pr; }
else break;
}
else
{
pr = (s - ) >> ;
if (heap[pr] > item){ heap[s] = heap[pr]; s = pr; }
else break;
}
}
heap[s] = item;
}
这是直接写堆的代码
#include<iostream>
#include<queue>
#include<functional>
#include<cstdio> using namespace std; int main(void)
{
int N, i;
int L1, L2, tmp;
long long ans = ; while (~scanf("%d", &N))
{
priority_queue<int, vector<int>, greater<int> >pque;
for (i = ; i < N; i++)
{
scanf("%d", &tmp);
pque.push(tmp);
}
while (pque.size() > )
{
L1 = pque.top();
pque.pop();
L2 = pque.top();
pque.pop(); ans += (long long)L1 + L2;
pque.push(L1 + L2);
};
printf("%lld\n", ans);
}
}
这是用的std，事实上呢用std是挺方便的，虽然稍微损失了一下性能，我直接用堆是472K,32ms，用std是920k,47ms，相差不大
另外这个思想还可以用来做著名的Huffman编码，其实Huffman以前写了一个，以后会贴出来看看