[贪心] Fence Repair （POJ-3253）

思路

  这道题其实和合并果子类似，此题可以采用题目叙述方式的逆过程来完成。题目是将木板切割成特定长度所花费的代价最小，我们可以转化为木板已经切好，将其拼接成为一块完整木板所花费的代价最小。每次取最小的两块进行拼接，就能保证最后拼成木板后所花费的代价最小。
  依旧采用优先队列进行切结，相比于合并果子，差别就在于队列中最后留下一个元素。

传送门

POJ-3253

AC代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int, vector<int>, greater<int> > wood;
int n;
long long ans = 0;

int main(){
    cin >> n;
    int temp;
    for(int i = 0; i < n; i++){
        cin >> temp;
        wood.push(temp); 
    }
    
    while(wood.size() > 1){
        int a = wood.top();
        wood.pop();
        int b = wood.top();
        wood.pop();
        int sum = a + b;
        ans += sum;
        wood.push(sum); 
    }
    cout << ans << endl;
    return 0;
}