1375 猴子偷桃（1440）

Jason1129

题目传送门

题目大意：
用一堆桃子和另一堆桃子合并，用合并的桃子再用另一堆桃子合并，直到只剩一堆桃子


明显的，体力等于两堆桃子之和，所以我们经过简单的推理得到
优先合并桃子少的，体力之和最少。

有了策略，我们就可以开始写代码了。
打住！！
n是30000，你用冒泡的n方的时间复杂度会超限。
sort的话，经过简单的计算，很明显超限。


分析一下我们的过程：
1.取出两个最少的桃子堆
2.合并成一个放回去
3.重新排序，返回第一步，直到只剩一堆


那么，能够轻松取出和推入元素的，并且能轻松排序的是


优先队列！！！


上代码！

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<string.h>
   
4. #include<algorithm>
   
5. #include<cmath>
   
6. #include<queue>
   
7. using namespace std;
   
8. priority_queue<long long,vector<long long>,greater<long long> > q;
   
9. //一定都要写long long
   
10. int arr[30000];
    
11. int n;
    
12. int main()
    
13. {
    
14.         int i,j,m;
    
15.         int a,b;
    
16.         long long sum=0;
    
17.         cin>>n;
    
18.         for (i=1;i<=n;i++)
    
19.         {
    
20.                 scanf("%d",&m);
    
21.                 //要写scanf，节省时间
    
22.                 arr[i]=m;
    
23.                 q.push(m);
    
24.         }
    
25.         while(q.size()>1)
    
26.         {
    
27.                 a=q.top();
    
28.                 q.pop();
    
29.                 b=q.top();
    
30.                 q.pop();
    
31.                 q.push(a+b);
    
32.                 //取出两堆，合并后放回
    
33.                 sum+=a+b;        
    
34.         }
    
35.         cout<<sum<<endl;
    
36.         return 0;
    
37. }
    
38. 
    
39.         

复制代码

求评价！！！

每日总结：
1.该题的策略，优先合并小的桃子堆，体力和最小
2.一定要写longlong和scanf，节省时间、
3.过程：1.取出两堆最小的，合并放回。2，重复第1步，直到队列长度（。size）为1

tiger

有版权吗？？

yuanbao

yuanbao

我的
https://bbs.singera.cn/forum.php ... &extra=page%3D1