<body>

kenshou

天空没有飞过的痕迹,但我已经努力飞过……

« Home | Next » | Next » | Next » | Next » | Next » | Next » | Next » | Next » | Next » | Next »

Packing Rectangles 题解

usaco都很久以前开始做的了,就做到1.4的这个放箱子的最小面积题目就放下了。这个题目其实也不难,关键就是要有耐心了。当然我这种对算法还不熟悉的笨人,就用笨方法来实现了那几个无趣的循环了。就是靠循环来穷举所有情况。
第一循环是对4个矩形的排序。
第二循环是对矩形长宽的交换。
然后就是6种情况的比较了。
/*
ID: kenshou1
LANG: C
TASK: packrec
*/
#include <stdio.h>
#include <stdlib.h>
void swap(int *a,int *b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
int getMax2Num(int a,int b){
    return (a>b)?a:b;
}
int getMax3Num(int a,int b,int c){
    int max=getMax2Num(a,b);
    return getMax2Num(max,c);
}
int getMax4Num(int a,int b,int c,int d){
    int max=getMax3Num(a,b,c);
    return getMax2Num(max,d);
}

int minArea=40001;//最小面积
int minWidth[1024],minHeight[1024];//最小面积对应的长宽数组
int pMin=0;//指向当前最小数组中保存的有效图案的个数
/**
*检测是否为最小面积
*/
void checkArea(int w,int h){
    int a=w*h;
    if(a<minArea){
        minArea=a;
        pMin=0;
        if(w>h){
            swap(&w,&h);
        }
        minWidth[pMin]=w;
        minHeight[pMin]=h;
        pMin++;
    }else if(a==minArea){
        if(w>h){
            swap(&w,&h);
        }
        minWidth[pMin]=w;
        minHeight[pMin]=h;
        pMin++;
    }
}

int farmcmpWidth(const void *va, const void *vb)
{
    return *(int *)va-*(int *)vb;
}
int farmcmpHeight(const void *va, const void *vb)
{
    return *(int *)vb-*(int *)va;
}

int main(void){
    FILE * fin=fopen("packrec.in","r");
    FILE* fout=NULL;
    int width[4];
    int height[4];
    int i=0;
    int a,b,c;//矩阵顺序的循环
    int x,y,z,n;//长宽的循环
    int w,h;//临时长度计算
    /*
    *初始化长宽
    */
    for(i=0;i<16;i++){
        fscanf(fin,"%d %d",&width[i],&height[i]);
    }
    fclose(fin);
   
    /**
    *外层矩阵顺序的4个循环(共4!=24种)
    */
    for(a=0;a<4;a++){
        swap(width,width+a);
        swap(height,height+a);
        for(b=1;b<4;b++){
            swap(width+1,width+b);
            swap(height+1,height+b);
            for(c=2;c<4;c++){
                swap(width+2,width+c);
                swap(height+2,height+c);
                /*
                *外层矩阵顺序循环结束开始内层长宽循环
                */
                for(x=0;x<=1;x++){
                    (x>0)?swap(width,height):x;
                    for(y=0;y<=1;y++){
                        (y>0)?swap(width+1,height+1):y;   
                        for(z=0;z<=1;z++){
                            (z>0)?swap(width+2,height+2):z;   
                            for(n=0;n<=1;n++){
                                (n>0)?swap(width+3,height+3):n;   
                                /*
                                *循环结束,枚举6种情况开始
                                */
                                /*
                                *第一种情况
                                *w=w1+w2+w3+w4;h=max(h1,h2,h3,h4)
                                */
                                w=width[0]+width[1]+width[2]+width[3];
                                h=getMax4Num(height[0],height[1],height[2],height[3]);
                                checkArea(w,h);
                                /*
                                *第二种情况
                                *w=max(w1+w2+w3,w4);h=max(h1,h2,h3)+h4
                                */
                                w=getMax2Num(width[0]+width[1]+width[2],width[3]);
                                h=getMax3Num(height[0],height[1],height[2])+height[3];
                                checkArea(w,h);
                                /*
                                *第三种情况
                                *w=max(w1+w2,w3)+w4;h=max(h1+h3,h2+h3,h4)
                                */
                                w=getMax2Num(width[0]+width[1],width[2])+width[3];
                                h=getMax3Num(height[0]+height[2],height[1]+height[2],height[3]);
                                checkArea(w,h);
                                /*
                                *第四种情况(第5种一样的了)
                                *w=w1+w2+max(w3,w4);h=max(h1,h3+h4,h2)
                                */
                                w=width[0]+width[1]+getMax2Num(width[2],width[3]);
                                h=getMax3Num(height[0],height[2]+height[3],height[1]);
                                checkArea(w,h);
                                /*
                                *第六种情况
                                *h=max(h1+h3,h2+h4)
                                *宽度需要细分
                                (1):h3>=h2+h4;w=max(w1,w3+w2,w3+w4)
                                (2):h3>h4 and h3<h2+h4;w=max(w1+w2,w2+w3,w3+w4)
                                (3):h4>h3 and h4<h1+h3;w=max(w1+w2,w1+w4,w3+w4)
                                (4):h4>=h1+h3;w=max(w2,w1+w4,w3+w4)
                                (5):h3=h4;w=max(w1+w2,w3+w4)
                                */
                                h=getMax2Num(height[0]+height[2],height[1]+height[3]);
                                if(height[2]>=(height[1]+height[3])){
                                    //1):h3>=h2+h4;w=max(w1,w3+w2,w3+w4)
                                    w=getMax3Num(width[0],width[2]+width[1],width[2]+width[3]);
                                   
                                }else if((height[2]>height[3])&&(height[2]<(height[1]+height[3]))){
                                    //(2):h3>h4 and h3<h2+h4;w=max(w1+w2,w2+w3,w3+w4)
                                    w=getMax3Num(width[0]+width[1],width[1]+width[2],width[2]+width[3]);
                                }else if((height[3]>height[2])&&(height[3]<(height[0]+height[2]))){
                                    //(3):h4>h3 and h4<h1+h3;w=max(w1+w2,w1+w4,w3+w4)
                                    w=getMax3Num(width[0]+width[1],width[0]+width[3],width[2]+width[3]);
                                }else if(height[3]>=(height[0]+height[2])){
                                    //(4):h4>=h1+h3;w=max(w2,w1+w4,w3+w4)
                                    w=getMax3Num(width[1],width[0]+width[3],width[2]+width[3]);
                                }else if(height[2]==height[3]){
                                    //(5):h3=h4;w=max(w1+w2,w3+w4)
                                    w=getMax2Num(width[0]+width[1],width[2]+width[3]);
                                }
                                checkArea(w,h);
                                /*
                                *枚举6种情况结束
                                */
                                (n>0)?swap(width+3,height+3):n;   
                            }
                            (z>0)?swap(width+2,height+2):z;   
                        }
                        (y>0)?swap(width+1,height+1):y;   
                    }
                    (x>0)?swap(width,height):x;
                }
               
                /*
                *内层长宽循环结束
                */
                swap(width+2,width+c);
                swap(height+2,height+c);
            }
            swap(width+1,width+b);
            swap(height+1,height+b);
           
        }
        swap(width,width+a);
        swap(height,height+a);
    }//外层4个矩形位置循环结束
   
    /*
    *对最小长宽数组进行排序
    */
    qsort(minWidth, pMin, sizeof(int), farmcmpWidth);
    qsort(minHeight, pMin, sizeof(int), farmcmpHeight);
   
    fout=fopen("packrec.out","w");
    fprintf(fout,"%d\n",minArea);
    w=0;
    for(i=0;i<pMin;i++){
        if(w<minWidth[i]){
            fprintf(fout,"%d %d\n",minWidth[i],minHeight[i]);
            w=minWidth[i];
        }
    }
    fclose(fout);
    exit(0);
}

标签:

leave a response