nyoj 55 懶省事的小明 優先隊列 multiset 還有暴力

懶省事的小明

時間限制： 3000 ms  |  記憶體限制： 65535 KB

難度： 3

描述

      小明很想吃果子，正好果園果子熟了。在果園裡，小明已經将所有的果子打了下來，而且按果子的不同種類分成了不同的堆。小明決定把所有的果子合成一堆。 因為小明比較懶，為了省力氣，小明開始想點子了:

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

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

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

輸入

第一行輸入整數N(0<N<=10)表示測試資料組數。接下來每組測試資料輸入包括兩行，第一行是一個整數n(1<＝n<=12000)，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai(1<＝ai<=20000)是第i種果子的數目。

輸出

每組測試資料輸出包括一行，這一行隻包含一個整數，也就是最小的體力耗費值。

樣例輸入

1
3 
1 2 9      

樣例輸出

15      

來源

[hzyqazasdf]原創

上傳者

hzyqazasdf

标準的哈夫曼樹，一直沒搞懂是怎麼算的，原來是這樣：終于搞懂是怎麼算的了。比如說4個數3 4 5 9.結果為40.怎麼算呢。就是先取出最小的兩個3 4.求和ans=3+4=7;然後把7放進所有的裡面程式設計7 5 9.取出最小的兩個 5 7。ans+=7+5+7=19；把這兩個數的和12放進去變成12 9.然後把剩下兩個取出來12 9.ans+=19+12+9=40. 這就是哈夫曼樹、 這裡直接用優先隊列實作。

優先隊列代碼：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <queue>

using namespace std;

struct mycomp
{
    bool operator()(const int &a,const int &b)
    {
        return a>b;
    }
};

int main()
{
    priority_queue<long long,vector<long long>,mycomp> pp;
    int T,n,x;
    scanf("%d",&T);
    while(T--)
    {
        long long ans=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&x);
            pp.push(x);
        }
        if(n==1)
        {
            printf("%d\n",x);
        }
        else
        {
            while(pp.size()>1)
            {
                int a=pp.top();
                pp.pop();
                int b=pp.top();
                pp.pop();
                int x=a+b;
                ans+=x;
                //printf("%d %d\n",a,b);
                pp.push(x);
            }

            printf("%lld\n",ans);
        }
        while(!pp.empty())
            pp.pop();
    }
    return 0;
}      

multiset多重集合容器實作

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

int main()
{

    int T,n,x;
    scanf("%d",&T);
    while(T--)
    {
        multiset<long long> v;
        long long ans=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&x);
            v.insert(x);
        }
        if(n==1)
            printf("%d\n",x);
        else
        {
            while(v.size()>1)
            {
                multiset<long long>::iterator it=v.begin();
                int a=*(it);
                int b=*(++it);
                v.erase(v.begin());
                v.erase(v.begin());
                ans+=(a+b);
                v.insert(a+b);
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}
      

牛人暴力代碼：時間24

#include<stdio.h>
#include<string.h>
int a[13000];
int b[13000];
int fronta,frontb,reara,rearb;
void qqqsort(int low,int high,int a[])
{
    int i,j,x;
    if(low>high)
        return;
    i=low;
    j=high;
    x=a[i];
    while(i!=j)
    {
        while(i<j&&a[j]>x)
            j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j&&a[i]<x)
            i++;
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=x;
    qqqsort(low,j-1,a);
    qqqsort(i+1,high,a);
}
int get()
{
    if(fronta==reara)
        return b[frontb++];
    if(frontb==rearb)
        return a[fronta++];
    return a[fronta]<b[frontb]?a[fronta++]:b[frontb++];
}
int main()
{
    long long ans,t;
    int n,m,i;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(i=0; i<m; i++)
            scanf("%d",&a[i]);
        qqqsort(0,m-1,a);
        fronta=frontb=rearb=ans=0;
        reara=m;
        for(i=0; i<m-1; i++)
        {
            t=get()+get();
            ans+=t;
            b[rearb++]=t;
        }
        printf("%lld\n",ans);
    }
    return 0;
}