POJ 3253 Fence Repair

最後一次cut 得到的是最短、次短的 plank

最後一次cut之後得到全部所需要的plank，，把他們的序列按照長度升序排列分别為：

L1、L2、L3....Ln

price+=（L1+L2）;

是以倒數第二次cut時的狀态應該為：（L1+L2）、L2、L3.....Ln-1

排序之後得到序列：L1、L2、L3....Ln-1(此時的L1、L2為“（L1+L2）、L2、L3.....Ln-1”中的最小、次小的數)

price+=（L1+L2）;

...

用優先隊列就展現為：對列保證元素從小道大排列，是以每次都是隊首兩元素出隊，其和入隊，直到隊列中隻有一個元素（所有plank的長度和）

//3253 已認證

#include <iostream>

#include<stdio.h>

#include<algorithm>

#include<queue>

using namespace std;

int main()

{

    int n;

    freopen("data.in","r",stdin);

    cin>>n;

    int tmp;

    long long prices=0;//這個地方快醉死了，雖然輸入的數字每個都可以用int存放，但是，N最大為2萬，每個數值最大為5萬，是以極有可能因為溢出而出現wrong answer錯誤，是以prices必須聲明為long long類型

    priority_queue<int,vector<int>,greater<int> > q;//greater<int>以小為優先，隊頭小隊尾大

    for(int i=0;i<n;i++)

    {

        cin>>tmp;

        q.push(tmp);

    }

    while(q.size()>1)

    {

        int temp1 = q.top();

        q.pop();

        int temp2 = q.top();

        q.pop();

        int sum = temp1+temp2;

        prices+=sum;

        q.push(sum);

    }

    cout<<prices<<endl;

    return 0;

}

//遞歸寫法，已認證