描述：
在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。
每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過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。

樣例輸入

3
1 2 9

樣例輸出

15

數據規模

對于30％的數據，保證有n<=1000：
對于50％的數據，保證有n<=5000；
對于全部的數據，保證有n<=10000。

?

思路

貪心做法，每次尋找當前剩下的最小的兩個相加

?

代碼

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int cmp(const void *,const void *); 5 6 int main() 7 { 8 int n,i,j,temp,sum=0; 9 int a[10010]; 10 scanf("%d",&n); 11 for(i=0;i<n;i++){ 12 scanf("%d",&a[i]); 13 } 14 /*sort(a,n);*/ 15 qsort(a,n,sizeof(a[0]),cmp); 16 for(i=0;i<n-1;i++){ 17 temp=a[i]+a[i+1]; 18 sum+=temp; 19 for(j=i+1;j<n;j++){ 20 if(a[j]<=temp) a[j-1]=a[j]; 21 else break; 22 } 23 a[j-1]=temp; 24 } 25 printf("%d",sum); 26 return 0; 27 } 28 29 int cmp(const void *a,const void *b) { 30 return (*(int *)a - *(int *)b); 31 }

?

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <limits.h> 4 5 struct fruit { 6 int energy; 7 int exist; 8 }; 9 10 int main() { 11 struct fruit a[20010]; 12 int n,i; 13 int min1,min2,min1no,min2no; 14 long sum; 15 sum=0; 16 scanf ("%d",&n); 17 for (i=0;i<n;i++) { 18 scanf ("%d",&a[i].energy); 19 a[i].exist=1; 20 } 21 if (n==1) { 22 printf ("%d\n",a[0].energy); 23 system("pause"); 24 return 0; 25 } 26 for (i=0;i<n;i++) { 27 int j; 28 if (i==n-1) { 29 for (j=0;j<n;j++) { 30 if (a[j].exist) { 31 printf ("%ld\n",sum); 32 system("pause"); 33 return 0; 34 } 35 } 36 } 37 min1no=-1; 38 min2no=-1; 39 min1=INT_MAX; 40 min2=INT_MAX; 41 for (j=0;j<n;j++) { 42 if (a[j].exist && a[j].energy < min1) { 43 if (min1 < min2) { 44 min2no=min1no; 45 min2=min1; 46 } 47 min1=a[j].energy; 48 min1no=j; 49 } 50 else if (a[j].exist && a[j].energy < min2) { 51 min2=a[j].energy; 52 min2no=j; 53 } 54 } 55 a[min1no].energy+=a[min2no].energy; 56 sum+=a[min1no].energy; 57 a[min2no].exist=0; 58 } 59 system("pause"); 60 return 0; 61 }

?

轉載于:https://www.cnblogs.com/yachen2018/p/8481730.html

總結

以上是生活随笔為你收集整理的Vijos p1097 合并果子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。