华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1901|回复: 5
打印 上一主题 下一主题

P1090 合并果子

[复制链接]

50

主题

215

帖子

619

积分

高级会员

Rank: 4

积分
619
跳转到指定楼层
楼主
发表于 2018-7-18 18:53:24 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 倚窗倾听风吹雨 于 2018-7-18 18:55 编辑

https://www.luogu.org/problemnew/show/P1090

题目描述在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n−1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
例如有 3 种果子,数目依次为 1 , 2 , 9 。可以先将 1 、 2 堆合并,新堆数目为 3 ,耗费体力为 3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12 ,耗费体力为 12。所以多多总共耗费体力 3+12=15 。可以证明 15 为最小的体力耗费值。
输入输出格式输入格式:

共两行。
第一行是一个整数 n(1≤n≤10000),表示果子的种类数。
第二行包含 n 个整数,用空格分隔,第 i 个整数 ai(1≤ai≤20000)是第 i 种果子的数目。

输出格式:

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于 2^31 。

输入输出样例输入样例#1
3
1 2 9

输出样例#1
15


说明对于30%的数据,保证有n≤1000 :
对于50%的数据,保证有n≤5000 ;
对于全部的数据,保证有n≤10000 。


回复

使用道具 举报

50

主题

215

帖子

619

积分

高级会员

Rank: 4

积分
619
沙发
 楼主| 发表于 2018-7-18 18:54:32 | 只看该作者
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,a[10010],w[10010],ans,n2;
  5. int i,j,k,t=1;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=1;i<=n;i++)
  10.     cin>>a[i];
  11.     sort(a+1,a+n+1);
  12.     i=1;j=1;
  13.     while(t<n)
  14.     {
  15.         if(a[i]>w[j] && w[j]!=0)k=w[j++];
  16.         else
  17.         {
  18.             if(a[i]!=0)k=a[i++];
  19.             else k=w[j++];
  20.         }
  21.         if(a[i]>w[j] && w[j]!=0)k+=w[j++];
  22.         else
  23.         {
  24.             if(a[i]!=0)k+=a[i++];
  25.             else k+=w[j++];
  26.         }
  27.         ans+=k;
  28.         w[++n2]=k;
  29.         t++;
  30.     }
  31.     cout<<ans;
  32.     return 0;
  33. }
复制代码
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
发表于 2018-7-19 22:49:38 来自手机 | 只看该作者
可以用优先队列!请看我的。
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. ///priority_queue<int>q; ///默认q里面的由大到小出列
  5. priority_queue<int, vector<int>, greater<int> > q;
  6. int n,x,i,x1,x2,s;

  7. int main()
  8. {
  9.     cin>>n;
  10.     for (i=1; i<=n; i++)
  11.     {
  12.         cin>>x;
  13.         q.push(x);
  14.     }

  15.     for (i=1; i<=n-1; i++)
  16.     {
  17.         x1=q.top();
  18.         q.pop();
  19.         x2=q.top();
  20.         q.pop();
  21.         x=x1+x2;
  22.         s=s+x;
  23.         ///cout<<s<<' ';
  24.         q.push(x);
  25.     }
  26.     cout<<s;



  27.     return 0;
  28. }

复制代码

回复 支持 反对

使用道具 举报

0

主题

30

帖子

91

积分

注册会员

Rank: 2

积分
91
地板
发表于 2018-7-24 19:34:27 | 只看该作者
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int n,h[100000];
  5. void swap(int r,int f)
  6. {
  7.     int t;
  8.     t=h[r];
  9.     h[r]=h[f];
  10.     h[f]=t;
  11.     return;
  12. }
  13. void siftdown()
  14. {
  15.     int t,flag=0,i=1;
  16.     while(i*2<=n && flag==0)
  17.     {
  18.         if(h[i]>h[i*2])
  19.             t=i*2;
  20.         else
  21.             t=i;
  22.         if(i*2+1<=n)
  23.             if(h[t]>h[i*2+1])
  24.                 t=i*2+1;
  25.         if(t!=i)
  26.         {
  27.             swap(t,i);
  28.             i=t;
  29.         }
  30.         else
  31.             flag=1;
  32.     }
  33.     return;
  34. }
  35. int main()   
  36. {   
  37.     int u;
  38.     int sum=0;
  39.     int x,y;
  40.     scanf("%d",&n);
  41.     for(int i=1;i<=n;i++)
  42.         scanf("%d",&h[i]);
  43.     sort(h+1,h+n+1);
  44.     u=n;
  45.     for(int i=1;i<=u-1;i++)
  46.     {
  47.         x=h[1];
  48.         h[1]=h[n];
  49.         h[n]=0;
  50.         n--;
  51.         siftdown();
  52.         y=h[1];
  53.         h[1]=x+y;
  54.         siftdown();
  55.         sum=sum+x+y;
  56.     }
  57.     printf("%d",sum);
  58.     return 0;
  59. }
复制代码
回复 支持 反对

使用道具 举报

2

主题

105

帖子

306

积分

中级会员

Rank: 3Rank: 3

积分
306
5#
发表于 2018-7-24 22:13:45 | 只看该作者
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <algorithm>
  7. using namespace std;
  8. int main(){
  9.         int n,i,j,a[10010]={0},min1=1,min2=2,all=0;
  10.         scanf("%d",&n);
  11.         for(i=1;i<=n;i++)
  12.         {
  13.                 scanf("%d",&a[i]);
  14.         }
  15.         sort(a+1,a+1+n);
  16.         for(i=1;i<=n-1;i++)
  17.         {
  18.                 for(j=1;j<=n;j++)
  19.                 {
  20.                         if(a[j]<a[min1])
  21.                         {
  22.                                 min2=min1;
  23.                                 min1=j;
  24.                         }
  25.                         else if(a[j]<a[min2]&&j!=min1)
  26.                                 min2=j;
  27.                 }
  28.                 all=all+a[min1]+a[min2];
  29.                 a[min2]+=a[min1];
  30.                 a[min1]=99999999;
  31.         }
  32.         printf("%d",all);
  33.     return 0;
  34. }
复制代码
回复 支持 反对

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
6#
发表于 2018-8-3 22:22:01 | 只看该作者
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. int n,s;
  5. int x,x1,x2,ans;
  6. priority_queue<int, vector<int> ,greater<int> >q;
  7. int main()
  8. {
  9.     cin>>n;
  10.     for(int i=1;i<=n;i++)
  11.         cin>>x,q.push(x);
  12.     for(int i=1;i<n;i++)
  13.     {
  14.         x1=q.top();
  15.         q.pop();
  16.         x2=q.top();
  17.         q.pop();
  18.         s=x1+x2;
  19.         ans+=s;
  20.         q.push(s);
  21.     }
  22.     cout<<ans;
  23.     return 0;
  24. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 13:20 , Processed in 0.103816 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表