堆学习笔记(未完待续)(洛谷p1090合并果子)
2019-08-16 08:02:29来源:博客园 阅读 ()
堆学习笔记(未完待续)(洛谷p1090合并果子)
上次讲了堆,别人都说极其简单,我却没学过,今天又听dalao们讲图论,最短路又用堆优化,问懂了没,底下全说懂了,我???,感觉全世界都会了堆,就我不会,于是我决定补一补;
——————来自百度百科
所以,堆其实就是一棵树;
大根堆:根节点比子节点权大;
小根堆:根节点比子节点权小;
了解到了这里,我觉得可以开始做题了;
T1合并果子
题面自己去洛谷看(我懒)
就是一个小根堆,每次取最小的两堆果子合并,排序会tle,所以用堆做,每次把合并后的再加入堆中就行了;
为了练习,先来一个手写堆;
详细看代码:
1 #include<iostream> 2 #include<cctype>//为了用isdigit 3 #include<cstdio> 4 using namespace std; 5 inline int read()//快读(isdigit用来判读入的是否是数字,据说比c>'0'这样的快) ; 6 { 7 int x=0,f=1;char c=getchar(); 8 while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} 9 while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} 10 return x*f; 11 } 12 int n,dui[10010],size;//dui用来存堆,size记录元素个数; 13 inline void swap(int &a,int &b){int t=a;a=b;b=t;return;}//交换值,&直接取地址交换,据说手写更快; 14 inline void up(int i)//把堆里元素向上移动 15 { 16 while(i>1)//直到查询到堆顶 17 if(dui[i]<dui[i/2])//如果i的元素比它父节点小,则交换两个元素; 18 { 19 swap(dui[i],dui[i/2]); 20 i/=2;//继续向上查询 21 } 22 else return; 23 } 24 inline void init(int x){dui[++size]=x;up(size);}//插入新的元素,size+1,然后看新元素是否要往上移动; 25 void down(int i)//向下移动大的元素 26 { 27 int s=i*2;//i的左儿子 28 while(s<=size) 29 { 30 if(dui[i*2+1]<dui[i*2])s++;//从i的左儿子和右儿子中选择较小的交换 31 if(dui[i]>dui[s])//如果i的权值比i的儿子的权值大,将i向下移动 32 { 33 swap(dui[i],dui[s]); 34 i=s;s=i*2;//注意!!!一定要i=s,我忘了会+1卡了好久,左子树和右子树一定要分清楚!!! 35 } 36 else return; 37 } 38 } 39 void shanchu(){dui[1]=dui[size--];down(1);}//合并后删除堆顶元素 ,并将元素向下传递; 40 int top(){return dui[1];}//取出堆顶元素 41 int main() 42 { 43 n=read(); 44 int a; 45 for(int i=1;i<=n;i++) 46 { 47 a=read();init(a); 48 } 49 long long answer=0; 50 while(size>=2) 51 { 52 int a1=top(); 53 shanchu(); 54 int a2=top(); 55 shanchu();//取出堆中最小的的两堆果子 56 answer+=(a1+a2); 57 init(a1+a2);//将合并后的一堆果子加入堆中 58 } 59 printf("%lld\n",answer); 60 return 0; 61 }View Code
偷懒做法,用STL
1 #include<iostream> 2 #include<set> 3 using namespace std; 4 multiset<int>dui;//multiset会自动帮你排序,从小到大,设它是一个堆 5 int n; 6 int main() 7 { 8 int a; 9 cin>>n; 10 for(int i=1;i<=n;i++) 11 { 12 cin>>a; 13 dui.insert(a);//把元素放进堆里 14 } 15 int ans=0; 16 for(int i=1;i<=n-1;i++) 17 { 18 int a1=*dui.begin();//dui.begin()返回的是地址,*取出地址里的值; 19 dui.erase(dui.begin());//删除堆顶,用地址传递 20 int a2=*dui.begin(); 21 dui.erase(dui.begin()); 22 ans+=(a1+a2); 23 dui.insert(a1+a2);//将合并后的加入堆 24 } 25 cout<<ans<<endl; 26 return 0; 27 }View Code
未完待续,如果我忘了可以催更(虽然没人看我博客)
原文链接:https://www.cnblogs.com/Frost-Delay/p/ju_ruo_de_dui_xue_xi_zhi_lv.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 如何0基础学习C/C++? 2020-06-06
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- vtk学习记录(三)——初识vtkRenderer 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- C++基础 学习笔记六:复合类型之数组 2020-04-25
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