FZU1327-合并果子的多种解法.ppt

《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[1000

7、5];intmin(intx,inty,intz){x=x

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);}}