[貪心策略]HAOI ：巧克力 chocolate 解題報告

試題描述

有一塊n*m的矩形巧克力，準備將它切成n*m塊。巧克力上共有n-1條橫綫和m-1條豎綫，你每次可以沿着其中的一條橫綫或豎綫將巧克力切開，無論切割的長短，沿着每條橫綫切一次的代價依次爲y1，y2，…，yn-1，而沿豎綫切割的代價依次爲x1，x2，…，xm-1。例如，對於下圖6*4的巧克力，我們先沿着三條橫綫切割，需要3刀，得到4條巧克力，然後再將這4條巧克力沿豎綫切割，每條都需要5刀，則最終所花費的代價爲y1+y2+y3+4*(x1+x2+x3+x4+x5)。

當然，上述簡單切法不見得是最優切法，那麼怎樣切割該塊巧克力，花費的代價最少呢？

輸入數據

第一行爲兩個整數n和m。

接下來n-1行，每行一個整數，分別代表x1，x2，…，xn-1。

接下來m-1行，每行一個整數，分別代表y1，y2，…，ym-1。

輸出數據

輸出一整數，爲切割巧克力的最小代價。

樣例輸入

6 4

2

1

3

1

4

4

1

2

樣例輸出

42

測試數據範圍

30%的數據，n<=100,m<=100

100%的數據，n<=10000，m<=10000

【分析】

貪心策略，先快速排序一下，不管橫豎，選擇最大的先切（有相等無所謂，當有幾個相等的最大值時，隨便選一個即可）。

【我的代碼】

 #include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int X[10001];
int Y[10001];

int Nx,Ny;

int cmp(const void *a,const void *b)
{
    return *((int *)b)-*((int *)a);
}

void init()
{
    scanf("%d %d\n",&Nx,&Ny);

    for (int i=1;i<=Nx-1;i++)
        scanf("%d\n",&X[i]);
    for (int i=1;i<=Ny-1;i++)
        scanf("%d\n",&Y[i]);
  
    qsort(X+1,Nx-1,sizeof(X[0]),cmp);
    qsort(Y+1,Ny-1,sizeof(Y[0]),cmp);
    return;
}


void greedy()
{
    int Tx=1,Ty=1;
    int ge=0;
    int tot=Nx+Ny-2;
    int T=0;
    while(ge<tot)
    {
        if(X[Tx]>=Y[Ty])
        {
            T+=(X[Tx]*Ty);
            Tx++;
            ge++;
            continue;
        }
        T+=(Y[Ty]*Tx);
        Ty++;
        ge++;
    }
    printf("%d\n",T);
}

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