873
九度題目1107：搬水果
題目1107：搬水果時間限製：1 秒內存限製：32 兆特殊判題：否提交：3463解決：1081
題目描述：
在一個果園裏，小明已經將所有的水果打了下來，並按水果的不同種類分成了若幹堆，小明決定把所有的
水果合成一堆。每一次合並，小明可以把兩堆水果合並到一起，消耗的體力等於兩堆水果的重量之和。當然經
過 n‐1 次合並之後，就變成一堆了。小明在合並水果時總共消耗的體力等於每次合並所耗體力之和。
假定每個水果重量都為 1，並且已知水果的種類數和每種水果的數目，你的任務是設計出合並的次序方案
，使小明耗費的體力最少，並輸出這個最小的體力耗費值。例如有 3 種水果，數目依次為 1，2，9。可以先將
1，2 堆合並，新堆數目為3，耗費體力為 3。然後將新堆與原先的第三堆合並得到新的堆，耗費體力為 12。所
以小明總共耗費體力=3+12=15，可以證明 15 為最小的體力耗費值。
輸入：
每組數據輸入包括兩行,第一行是一個整數 n(1=n=10000),表示水果的種類數，如果 n 等於 0 表示輸入
結束，且不用處理。第二行包含 n 個整數，用空格分隔，第 i 個整數(1=ai=1000)是第 i 種水果的數目。
輸出：
對於每組輸入，輸出一個整數並換行，這個值也就是最小的體力耗費值。輸入數據保證這個值小於 2^31。
樣例輸入：
3
9 1 2
0
樣例輸出：
15
來源：
2011年吉林大學計算機研究生機試真題
思路：貪心算法，每次找出數組裏麵最小的兩個數組合，用sort排序一次一次求出最小的兩個值一定會超時，所以用特殊
的選擇排序，每次都使數組前兩個數最小（隻排前兩個），測試數組可能很大，其餘後麵的沒必要排序，節省
時間。
其中要注意的一點，找出數組中最小值時，隻需要統計下標，跳出循環後再讓他與首元素進行交換，防止在循
環內交換次數過多造成超時！
AC代碼：
#include<stdio.h>
#include<string.h>
int a[10010];
int main()
{
int i,j,n,t,x,k,sum;
while(scanf("%d",&n),n!=0)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
x=0;sum=0;
while(x<n-1)
{
for(i=x;i<x+2;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[k]>a[j]) k=j; //標記最小值
}
t=a[i];//在循環外麵交換，不需要每次交換，節省了交換時間
a[i]=a[k];
a[k]=t;
}
a[x+1]=a[x]+a[x+1];
sum+=a[x+1];
x++;
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 12:56:41