华师一附中OI组

标题: P1090 合并果子 [打印本页]

---

作者: 倚窗倾听风吹雨    时间: 2018-7-18 18:53
标题: P1090 合并果子


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 。

---

作者: 倚窗倾听风吹雨    时间: 2018-7-18 18:54

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. }

复制代码

---

作者: admin    时间: 2018-7-19 22:49
可以用优先队列！请看我的。

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. 
   
8. int main()
   
9. {
   
10.     cin>>n;
    
11.     for (i=1; i<=n; i++)
    
12.     {
    
13.         cin>>x;
    
14.         q.push(x);
    
15.     }
    
16. 
    
17.     for (i=1; i<=n-1; i++)
    
18.     {
    
19.         x1=q.top();
    
20.         q.pop();
    
21.         x2=q.top();
    
22.         q.pop();
    
23.         x=x1+x2;
    
24.         s=s+x;
    
25.         ///cout<<s<<' ';
    
26.         q.push(x);
    
27.     }
    
28.     cout<<s;
    
29. 
    
30. 
    
31. 
    
32.     return 0;
    
33. }
    
34. 
    

复制代码

---

作者: walk_alone    时间: 2018-7-24 19:34

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. }

复制代码

---

作者: 吴语林    时间: 2018-7-24 22:13

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. }

复制代码

---

作者: 黄煦喆    时间: 2018-8-3 22:22

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. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2