POJ3253-Fence Repair

题目链接：点击打开链接

将木板切下，每次切的花费为切下的长度，求最小花费。

用哈夫曼思想就是，每次找两个最小的合成一个，再放进队列，直到剩下最后一个。

//448K 16MS //C++ 589B #include <queue> #include <cstring> #include <cstdio> using namespace std; struct cmp { bool operator ()(const long long int &a,const long long int &b)const { return a>b; } }; int main() { priority_queue<long long int,vector<long long int>,cmp> q; int i,j,n; long long int sum=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&j); q.push(j); } while(q.size()>1) { int a=q.top(); q.pop(); int b=q.top(); q.pop(); sum+=a+b; q.push(a+b); } printf("%lld\n",sum); }