菜鸡哈屠教你合并果子
2019-08-16 07:54:11来源:博客园 阅读 ()
菜鸡哈屠教你合并果子
我们先来看题:
(图片来自洛谷)
题解:这是一道贪心。每次取最小两堆合并即可。 证明的话,自己画一棵"合并树",就会很清晰了。 每一堆果子用数组记录,就能AC,用不着优化。
AC代码:
不过!!!
还有更快的。那就是 优先队列 。
优先队列,就是优先的队列,内部是由"堆"来实现。 我之前连半点数据结构都没有提到过。不过,没关系!!我接下来会更新关于这一方面的内容。
这里简单介绍一下 优先队列 。 它是个队列,你把数据存进去,C++的STL自动帮帮你排序(你可以这么理解吧)。
基本操作:
1 q.top(); 查找队列顶部。 1 q.pop(); 弹出队列首元素。 1 q.top(); 返回值为队列首元素。
细节以后我会慢慢讲。
AC代码:
1 #include <bits/stdc++.h> 2 #define N 10010 3 using namespace std; 4 int n,a,s; 5 priority_queue <int,vector<int>,greater<int> >b; 6 int main(){ 7 cin>>n; 8 for(int i=1;i<=n;i++) {cin>>a; b.push(a);} 9 while(b.size()>=2){ 10 int x=b.top(); 11 b.pop(); 12 int y=b.top(); 13 b.pop(); 14 s+=x+y; 15 b.push(x+y); 16 } 17 cout<<s<<endl; 18 return 0; 19 }
感谢大家的阅读。。。安利我自己的博客中。。。
原文链接:https://www.cnblogs.com/tushukai/p/11252328.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【做题笔记】P1090 合并果子 2020-02-14
- BJFU-225-基于链表的两个递增有序序列的合并 2019-10-28
- 堆学习笔记(未完待续)(洛谷p1090合并果子) 2019-08-16
- C++实现多组数据合并输出 2019-08-16
- 石子合并问题--直线版 HRBUST - 1818 2019-08-16
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