[USACO][Section 1.4][模拟] Packing Rectangles

前言：

这是一道令人望而却步的题，没有什么技术难度却又很需要勇气。解决它所需要花费的时间实际并不长，但就是怕麻烦的这种心理障碍让我迟迟无法下手，真需要好好反省一下。

题目大意：

给出4个矩形的长宽，求能包含4个矩形的最小矩形的面积，并输出其长宽。

思路：

题目通过图片形式给出了6种基本组合方式（4、5其实是一种），只需要把4个矩形插入相应位置即可。通过全排列遍历所有插入方案，再通过四重循环遍历所有翻转方案（横放或竖放）。简单计算下：需要遍历一共5*4!*2^4个方案后才能确定最终答案。

代码：

/*
ID: lujunda1
LANG: C++
PROG: packrec
*/
#include
#include
#include
#include
using namespace std;
int rect[4][2];
//rectangle 用于存储4个矩形的长宽，rect[i][0]表示第i个矩形的长度，rect[i][1]表示其宽度。 
int order[4]={0,1,2,3};
//顺序数组，每个基本排列中，交换矩形的位置。共有24种组合。 
int tmp[4][2];
//存储通过顺序处理和翻转处理后的矩形信息。 
int t[4];
//t[i]为1时，表示第i个矩形需要翻转90°，为0时不需要翻转。 
int min_size=1000000;
//表示最小面积 。 
int total;
//表示最小面积包含的方案数量。 
map mark;
struct result
{
    int length;
    int width;
}res[100];
//存储最小面积包含的所有方案。 
int max(int a,int b)
{
    return a>b?a:b;
}
int max(int a,int b,int c)
{
    return max(max(a,b),c);
}
int max(int a,int b,int c,int d)
{
    return max(max(a,b,c),d);
}
int cmp(const void* m,const void* n)
{
    return (*(result*)m).width-(*(result*)n).width;
}
void change()
//根据order[]和t[]来生成tmp[]。 
{
    for(int i=0;i<4;i++)
        for(int j=0;j<=1;j++)
            tmp[i][j]=rect[order[i]][j];
    //顺序处理 
    for(int i=0;i<4;i++)
        if(t[i])
            swap(tmp[i][0],tmp[i][1]);
    //翻转处理 
}
void updata(int length,int width)
//根据当前大矩形长宽来更新res[]。 
{
    if(length<width)
    //应题目的格式要求 
        swap(length,width);
    if(length*width<min_size)
    //当前大矩形的面积比min_size小时，更新minsize和res[]还有total以及mark[]。 
    {
        total=1;
        res[0].length=length;
        res[0].width=width;
        min_size=length*width;
        mark.clear();
        mark[width]=true;
    }
    else if(length*width==min_size&&!mark[width])
    //当前大矩形的面积与min_size相等且有新方案时，更新res[]和total。 
    {
        res[total].length=length;
        res[total++].width=width;
        mark[width]=true;
    }
}
void plan_1()
//根据题目所给的图，考虑5种情况（第4、第5个图为同一种情况）。根据每种情况求出大矩形的长宽。 
{
    int width=tmp[0][1]+tmp[1][1]+tmp[2][1]+tmp[3][1];
    int length=max(tmp[0][0],tmp[1][0],tmp[2][0],tmp[3][0]);
    updata(length,width);
}
void plan_2()
{
    int width=max(tmp[0][1]+tmp[1][1]+tmp[2][1],tmp[3][1]);
    int length=max(tmp[0][0],tmp[1][0],tmp[2][0])+tmp[3][0];
    updata(length,width);
}
void plan_3()
{
    int width=max(tmp[0][1]+tmp[1][1],tmp[2][1])+tmp[3][1];
    int length=max(max(tmp[0][0],tmp[1][0])+tmp[2][0],tmp[3][0]);
    updata(length,width);
}
void plan_4()
{
    if(tmp[0][1]<=tmp[1][1])
    {
        int width=tmp[1][1]+tmp[2][1]+tmp[3][1];
        int length=max(tmp[0][0]+tmp[1][0],tmp[2][0],tmp[3][0]);
        updata(length,width);
    }
}
void plan_5()
{
    if(tmp[0][1]<=tmp[1][1]&&tmp[1][0]<=tmp[3][0]&&tmp[0][1]+tmp[2][1]<=tmp[1][1]+tmp[3][1])
    {
        int width=tmp[1][1]+tmp[3][1];
        int length=max(tmp[0][0]+tmp[1][0],tmp[2][0]+tmp[3][0]);
        updata(length,width);
    }
}
void get_min()
//针对change()及plan_*()的调用。 
{
    change();
    plan_1();
    plan_2();
    plan_3();
    plan_4();
    plan_5();
}
void func()
{
    for(int i=0;i<24;i++)
    //四个数的全排列共有4!=24种情况。 
    {
        for(t[0]=0;t[0]<=1;t[0]++)
            for(t[1]=0;t[1]<=1;t[1]++)
                for(t[2]=0;t[2]<=1;t[2]++)
                    for(t[3]=0;t[3]<=1;t[3]++)
                    //4个矩形翻转共有2^4=16种情况。 
                        get_min();
        next_permutation(&order[0],&order[4]);
        //调用next_permutation()寻找order[]的下一个排列。 
    }
}
int main()
{
    freopen("packrec.in","r",stdin);
    freopen("packrec.out","w",stdout);
    for(int i=0;i<4;i++)
        scanf("%d%d",&rect[i][0],&rect[i][1]);
    func();
    qsort(res,total,sizeof(res[0]),cmp);
    printf("%d\n",min_size);
    for(int i=0;i<total;i++)
        printf("%d %d\n",res[i].width,res[i].length);
}

发表回复取消回复