P1334 瑞瑞的木板

-----------------------------

堆的水题

---------------------------------------------------

MIku

---------------------------------------------------

这道题第一眼应该会很，懵逼，啥？搜索？贪心？

然后你仔细看看题目

“将长度为21的木板，第一次切割为长度为8和长度为13的，消耗21个单位的能量，第二次将长度为13的木板切割为长度为5和8的，消耗13个单位的能量，共消耗34个单位的能量，是消耗能量最小的方案。”

有没有发现什么？

8+13=21而13就等于5+8

没错，这道题应该倒着做！

我们应该是倒着拼木板，最后拼出我们需要的

（哎，这不就是合并果子吗？）

---------------------------------------------------

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 using namespace std;
 5 priority_queue<long long> wood;
 6 long long n;
 7 long long x;
 8 int main(){
 9     cin>>n;
10     for(long long i=1;i<=n;++i){
11         cin>>x;
12         wood.push(-x);
13     }
14     long long ans=0;
15     while(wood.size()&&wood.size()>1){
16         long long x,y;
17         x=-wood.top();
18         wood.pop();
19         y=-wood.top();
20     //    cout<<x<<" "<<y<<endl;
21         wood.pop();
22         ans+=(x+y);
23         wood.push(-(x+y));
24     }    
25     cout<<ans;
26     return  0;
27 }