3214. 锯栅栏

include

include

using namespace std;
/典型的优先队列
注意模板长度会超过int！！！/
int main(){
int N;
int temp;
int temp2;
cin>>N;
if(N==1){
cout<<0;
return 0;
}
if(N==2){
cin>>temp;
cin>>temp2;
cout<,greater\> q; for(int i =0;i\>temp;
q.push(temp);
}
while(q.size()>1){
temp = q.top();
q.pop();
temp2 = q.top();
q.pop();
sum+=(temp+temp2);
q.push(temp+temp2);
}
cout<<sum;
}

把木板切割的过程反过来看，就是将两个木板粘起来的cost是两块木板长度之和，那么有n条木板，怎样的连接顺序使得将所有的木板粘起来的cost最小。

原问题就变成了huffman树的问题，只需要每次从所有木板中找到最短的两个然后将他们粘起来的长度作为一块新的木板加入到原来的木板堆中，重复以上过程直到所有的木板全部相连。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    int N;
    cin >> N;
    priority_queue<ll, vector<ll>, greater<>> a;
    int tmp;
    while (N--) {
        cin >> tmp;
        a.push(tmp);
    }
    ll min1;
    ll min2;
    ll ans = 0;
    while (a.size() > 1) {
        min1 = a.top();
        a.pop();
        min2 = a.top();
        a.pop();
        ans += (min1 + min2);
        a.push(min1 + min2);
    }
    cout << ans << endl;
    return 0;
}