大神的世界

題意:

現有7種方形箱子

邊長依序為 1  2  4  8  16  32  64

給你個別所需數量

請你找出可容納所有箱子之最短邊長 方形紙箱

輸入以-1代表結束

想法:

箱子由大至小放入

先放右邊再放下面

須時時保持最短邊長

保持最短邊長方法，右邊下面可放則放

不可放時，再新增空間於右上

例如

1 2 3 0 0 0 0

最大邊長為4

****
****
****
****

**** ****

**** ****

**** ****

**** ****

**** ****

**** ****

**** ****

**** ****

****

****

****

****

最大邊長為2

**** ****

**** ****

**** ****

**** ****

**** **

****

****

****

**** ****

**** ****

**** ****

**** ****

**** ** **

****

****

****

**** ****

**** ****

**** ****

**** ****

**** ** **

**** **

****

****

最大邊長為1

**** ****

**** ****

**** ****

**** ****

**** ** **

**** ** *

****

****

=> 紙箱之最短邊長為8

迴圈

輸入所需箱子數量

自最長箱子開始

若右邊、下面沒位置

將箱子放於右上角

右邊空間新增原紙箱邊長(寬/列)*箱子邊長(長/行)

新紙箱邊長增加箱子邊長

下面空間新增新紙箱邊長(長/行)*箱子邊長(寬/列)

先放右邊，再放下面

放置規則:

若空間可完全容納則該邊長剩餘之所有箱子放入

若空間不可完全容納則放置可容納之最大數量

#include <iostream>

using namespace std;

int box[7];
int box_length[7] = {1, 2, 4, 8, 16, 32, 64};

void padding(int *space, int id);

int main()
{

    int col, row, len, id;

    while(cin >> box[0] && box[0] != -1)
    {
        cin >> box[1] >> box[2] >> box[3] >> box[4] >> box[5] >> box[6];

        col = row = len = 0;
        for(id = 6; id>=0; id--)
        {
            while(box[id])
            {
                if(col < box_length[id] && row < box_length[id])
                {
                    row = len*box_length[id];
                    len += box_length[id];
                    col = len*box_length[id];
                }

                padding(&row, id);
                padding(&col, id);
            }
        }

        cout << len << endl;
    }
    return 0;
}

void padding(int *space, int id)
{
    int load, box_space = box_length[id]*box_length[id];

    if(*space >= box_space)
    {
        *space / box_space >= box[id]? load = box[id] : load = *space / box_space;

        *space -= load*box_space;
        box[id] -= load;
    }
}