【做题笔记】P1090 合并果子
2020-02-14 16:01:49来源:博客园 阅读 ()
【做题笔记】P1090 合并果子
题目大意:给定 \(n\) 个数,每次可以任意选两个数 \(a_i,a_j\) 相加,把相加的结果作为一个新数继续执行此操作,直到只剩一个数为止。现要求使最后得出的这个数最小。
一个显然的贪心策略:每次选最小的两个数相加,得到一个新数,然后继续。但是,如果按照这样的思路,那么每次得到新数后这个序列的单调性就有可能会被破坏。
如何解决呢?很显然的一种方法,将新数加入序列后,再把这个序列排序。然而这样做似乎会超时。C++ STL 中提供了一种巧妙地解决方法:\(\mathtt{priority\_queue}\)。它地本质是建一个二叉堆,然后每当插入一个数,就维护这个二叉堆。那么显然,在这个题中,我们需要建一个小根堆,使较小的元素总是先被取出进行操作。
然后需要解决一个问题:
如何建立小根堆(使用\(\mathtt{priority\_queue}\))?
这样:priority_queue<int,vector<int>,greater<int> >q;
。其中第一个 int
代表小根堆中存储的数据类型, vector<int>
代表存储的方式(vector
就是数组), greater<int>
就是从小到大(即小根堆)。然后大根堆的话就是 priority_queue<int,vector<int>,less<int> >q;
。
于是,做法就呼之欲出了:没读入一个数字,就插入小根堆中。然后,当元素个数大于等于 2 时循环,每次取出队首的两个元素相加,答案加上这个数字,再令新数入队即可。
请注意:这里为什么循环条件时元素个数大于等于 2而不是 队列不为空 呢?用兔队的一句话来回答:
参考代码:
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int n,w;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
long long ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&w);q.push(w);}
while(q.size()>=2)
{
int x=q.top();q.pop();
int y=q.top();q.pop();
x+=y;
ans+=x;
q.push(x);
}
printf("%lld\n",ans);
return 0;
}
原文链接:https://www.cnblogs.com/Nicest1919/p/12309318.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- C++基础 学习笔记五:重载之运算符重载 2020-04-23
- C++基础 学习笔记四:重载之函数重载 2020-04-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash