NOIP2004提高組複賽 合併果子 fruit 解題報告

二、合併果子

(fruit.pas／dpr／c／cpp)

【問題描述】

在一個果園裏，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

每一次合併，多多可以把兩堆果子合併到一起，消耗的體力等於兩堆果子的重量之和。可以看出，所有的果子經過n-1次合併之後，就只剩下一堆了。多多在合併果子時總共消耗的體力等於每次合併所耗體力之和。

因爲還要花大力氣把這些果子搬回家，所以多多在合併果子時要儘可能地節省體力。假定每個果子重量都爲1，並且已知果子的種類數和每種果子的數目，你的任務是設計出合併的次序方案，使多多耗費的體力最少，並輸出這個最小的體力耗費值。

例如有3種果子，數目依次爲1，2，9。可以先將1、2堆合併，新堆數目爲3，耗費體力爲3。接着，將新堆與原先的第三堆合併，又得到新的堆，數目爲12，耗費體力爲12。所以多多總共耗費體力=3+12=15。可以證明15爲最小的體力耗費值。

【輸入文件】

輸入文件fruit.in包括兩行，第一行是一個整數n(1<＝n<=10000)，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai(1<＝ai<=20000)是第i種果子的數目。

【輸出文件】

輸出文件fruit.out包括一行，這一行只包含一個整數，也就是最小的體力耗費值。輸入數據保證這個值小於231。

【樣例輸入】

3 1 2 9

【樣例輸出】

15

【數據規模】

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

（感謝BYVoid大牛的OpenCC提供強力的正體中文轉換引擎！）

【分析】

注意這道題不是石子歸併類DP！本題的策略是貪心，每次找到最小的兩堆果子，將它們合併，代價就是這兩堆果子的數目和。

   本題可以用快速排序做，每次合併前先快排一次，不過這樣比較慢，最後幾組只能擦著1秒的邊過。

    我第一次寫該題用了靜態鏈表，是插入排序的一種，效率稍好，最後幾組測試數據平均0.6s多。

    我第二次寫該題時，用了本題的標準算法——堆排序。每次合併前維護一下這個小根堆，時間複雜度很低，我的程序沒有一組的運行時間超過0.1s。

根優化的小根堆算法：見本文

本題幾種算法的橫向對比！

 快速排序：3.749 s

 本文靜態鏈表：2.453 s 

 本文小根堆：0.109 s

 此文小根堆一：0.053 s

 此文小根堆二：0.037 s

【代碼】

<1>用鏈表寫的。

#include <fstream>
using namespace std;   
ifstream fin("fruit.in");
ofstream fout("fruit.out");
class data
{
public:
    int key;
    //Other members HERE...
    int sen;//前驱
    int next;//后继
};
data A[200000];
int top;//链表中元素的个数

void Insert(int key)
{
    int point=0;
    while (key>A[point].key)
    {
        point=A[point].next;
    }
    //Create a new node
    A[top].key=key;
    A[top].next=point;
    A[top].sen=A[point].sen;
   
    A[point].sen=top;//后继的前驱等于自己
   
    A[A[top].sen].next=top;//前驱的后继等于自己
   
    top++;
}

void DeleteOne(int key)
{
    int point=A[0].next;
    while(A[point].next!=-1)
    {
        if(A[point].key==key)
        {
            A[A[point].sen].next=A[point].next; //自己前驱的后继等于自己的后继
            A[A[point].next].sen=A[point].sen;  //自己后继的前驱等于自己的前驱
            return; //跳出函数
        }
        point=A[point].next;
    }
}

void print()
{
    int point=A[0].next;
    while(A[point].next!=-1)
    {
        fout<<A[point].key<<endl;
        point=A[point].next;
    }
}
void debug()
{
    for (int i=0;i<top;i++)
        fout<<i<<" "<<A[i].key<<" "<<A[i].sen<<" "<<A[i].next<<endl;
}

int GetMinElem()
{
    int point=A[0].next;
    return A[point].key;
}

int main()
{

    //Initialize
    A[0].key=-1;A[0].next=1;A[0].sen=-1;
    A[1].key=0Xfffffff;A[1].next=-1;A[0].sen=0;
    top=2;
    int num,key;
    fin>>num;
    for (int i=0;i<num;i++)
    {
        fin>>key;
        Insert(key);//插入一个关键字
    }
   
    int liu=num;
    int cost=0;
    //debug();
    while (liu!=1)
    {
        int m=GetMinElem();
        DeleteOne(m);
        int n=GetMinElem();
        DeleteOne(n);
        //fout<<m<<" "<<n<<endl<<endl;
        cost+=(m+n);
        Insert(m+n);
        liu--;
    }
    //print();
    fout<<cost<<endl;
    return 0;
}

<2>用小根堆寫的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN=0xfffffff;
int N;
int T;
int F[10001];


void init()
{
    scanf("%d\n",&N);
    T=N;
    for (int i=1;i<=N;i++)
        cin>>F[i];
}

void downshift(int i)
{
    int j,x;
    x=F[i];
    j=i<<1;
    while (j<=T)
    {
        if (F[j]>F[j+1] && j+1<=T)
            j++;
        if (x>F[j])
        {
            F[i]=F[j];
            i=j;
            j=j<<1;
        }
        else
            break;
    }
    F[i]=x;
}

void HeapWorks()
{
    long long ans=0;
    for (int i=N/2;i>=1;i--)
        downshift(i);
    int k;
    for (int i=1;i<=N-1;i++)
    {
        if (F[2]<F[3])
            k=2;
        else
            k=3;
        ans+=F[1]+F[k];
        F[1]+=F[k];
        downshift(1);
        F[1]=MAXN;
        downshift(1);
    }
    cout<<ans<<endl;
}

int main()
{ 
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout); 
    init();
    HeapWorks();
    return 0;
}