欢迎来到天天文库
浏览记录
ID:62049159
大小:775.50 KB
页数:10页
时间:2021-04-13
《FZU1327-合并果子的多种解法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、FZU1327(合并果子)MrSunday题意就是找出每次合并后剩下的堆里面最小的两堆,然后再次合并,每次合并的新堆的值就是每次所得的分,直到只剩下一堆为止345605670+711711+71818+1836解题思路一、贪心:快排加插排(没有牛排)二、优先队列(ORZ...)三、堆排序四、模拟(我自创的,反正现在再看代码连我都想说,这货当初都干了什么)#include#includeintcmp(constvoid*a,constvoid*b){return*(i
2、nt*)b-*(int*)a;}intmain(){intn,v[10005];while(scanf("%d",&n)!=EOF){inti,j,total=0;for(i=1;i<=n;i++)scanf("%d",&v[i]);qsort(v+1,n,sizeof(v[0]),cmp);//快排for(i=n;i>=2;i--){v[i]+=v[i-1];//每次合并两堆total+=v[i];//累加得分for(j=i-2;v[i]>v[j]&&j>=1;j--)v[j+1]=v[j];v[
3、j+1]=v[i];//插排}printf("%d",total);}return0;}优先队列priority_queueq;empty()如果队列为空返回真pop()删除对列首元素push()加入一个元素size()返回优先队列中拥有的元素个数top()返回优先队列首元素#include#includeusingnamespacestd;intmain(){priority_queue,greater>q;in
4、tn,a,i;while(~scanf("%d",&n)){intans=0;while(!q.empty())q.pop();for(i=0;i1){a=q.top();q.pop();a+=q.top();q.pop();q.push(a);ans+=a;}printf("%d",ans);}return0;}#include#includeintn,a[100
5、05]={0};voidminheap(intx){intmin=x,t;intl=2*x;//左子节点intr=2*x+1;//右子节点if(l<=n&&a[l]6、"%d",&a[i]);for(i=n/2;i>0;i--)minheap(i);intans=0,tmp;for(i=1;i#includeinta[10005],b[10007、5];intmin(intx,inty,intz){x=x8、[l]+b[r],b[r]+b[r+1]);if(temp==a[l]+a[l+1])l+=2;elseif(temp==b[r]+b[r+1])r+=2;elsel++,r++;b[t++]=temp;ans+=temp;}printf("%d",ans);}}
6、"%d",&a[i]);for(i=n/2;i>0;i--)minheap(i);intans=0,tmp;for(i=1;i#includeinta[10005],b[1000
7、5];intmin(intx,inty,intz){x=x8、[l]+b[r],b[r]+b[r+1]);if(temp==a[l]+a[l+1])l+=2;elseif(temp==b[r]+b[r+1])r+=2;elsel++,r++;b[t++]=temp;ans+=temp;}printf("%d",ans);}}
8、[l]+b[r],b[r]+b[r+1]);if(temp==a[l]+a[l+1])l+=2;elseif(temp==b[r]+b[r+1])r+=2;elsel++,r++;b[t++]=temp;ans+=temp;}printf("%d",ans);}}
此文档下载收益归作者所有