【poj 3253 Fence Repair】【优先队列】【切木板为给定的几块，每次的代价为切的两段长度】

队列】【切木板为给定的几块，每次的代价为切的两段长度】"/>

【poj 3253 Fence Repair】【优先队列】【切木板为给定的几块，每次的代价为切的两段长度】

【链接】

【题意】

把一块木板切成给定长度的几块，每次切的代价为切下的两块的长度

【思路】

反向思维，将一块木块切成几分，相当于是几块木板合成一份，代价为两块木块的和，求合成一块木块的代价的最小值，就很好理解用优先队列维护即可。

【代码】

#include<queue>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 1e5 + 6;
priority_queue<int,vector<int>,greater<int> >q;int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {int m;scanf("%d", &m);q.push(m);}ll ans=0;int a, b;int mi = q.top();while (q.size()>1) {a = q.top(); q.pop();b = q.top(); q.pop();ans += a+b;q.push(a + b);}printf("%lld\n", ans);
}