贪心+模拟-poj-1017-Packets - c++编程基础

题目大意：

有1*1,2*2,3*3,4*4,5*5,6*6的产品若干个，问最少需要用多少个6*6的包装盒把所有的产品都装好。

解题思路一：

显然6*6,5*5,4*4的产品每次只能放一个，且放完后只能放1*1的产品。对于3*3的格子，设置数组lim[i][j]表示放了i个j*j的产品后最多还能放多少个2*2的。

显然lim[4][3]=0,lim[3][3]=1,lim[2][3]=3,lim[1][3]=5,lim[0][3]=9; lim[1][4]=5;

Max[i]表示当放i*i的产品时最多能放多少个。

然后每次从大往小放，有多的空间就尽可能的放2*2和1*1.注意有时2*2的产品数量比较少，此时可以放更多的1*1。

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define LL long long  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#define M 1000000007  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 10  
int num[Maxn];  
int lim[Maxn][Maxn],Max[Maxn];  
  
int main()  
{  
  
    memset(lim,0,sizeof(lim));  
    lim[4][3]=0,lim[3][3]=1,lim[2][3]=3,lim[1][3]=5,lim[0][3]=9;  
    lim[1][4]=5;  
    Max[6]=1,Max[3]=4,Max[4]=1,Max[5]=1,Max[2]=9,Max[1]=36;  
  
    while(scanf("%d",&num[1]))  
    {  
        int flag=num[1];  
  
        for(int i=2;i<=6;i++)  
        {  
            scanf("%d",&num[i]);  
            flag+=num[i];  
        }  
        if(!flag)  
            break;  
  
        int ans=0;  
        for(int i=6;i>=2;i--)  
        {  
            if(!num[i])  
                continue;  
            if(num[i]>=Max[i]) //比能放的最多的还多，不止放一个  
            {  
                int tmp=num[i]/Max[i]; //放的个数  
                ans+=tmp;  
                num[i]%=Max[i]; //剩下的个数  
  
                int tt=tmp*lim[Max[i]][i];//可以填补的2*2的个数  
  
                if(num[2])  
                {  
                    if(num[2]>=tt) //2*2的产品比较多的话，可以全部添进去  
                        num[2]-=tt;  
                    else  
                    {  
                        tt=num[2]; //比较少的话只添一部分  
                        num[2]=0;  
                    }  
  
                }  
                if(num[1]) //根据2*2的占用情况，添加1*1  
                {  
                    num[1]-=36*tmp-tt*4-i*i*Max[i]*tmp;  
                    if(num[1]<0)  
                        num[1]=0;  
                }  
  
            }  
            if(num[i]) //剩余的  
            {  
                ans++; //再添加一个  
                int tt=lim[num[i]][i]; //2*2的个数  
  
                if(num[2])  
                {  
                    if(tt>




=num[2])  
                    {  
                        tt=num[2];  
                        num[2]=0;  
                    }  
                    else  
                        num[2]-=tt;  
                }  
                if(num[1]) //1*1的可添加的个数  
                {  
                    num[1]-=36-tt*4-num[i]*i*i;  
                    if(num[1]<0)  
                        num[1]=0;  
                }  
                num[i]=0;  
            }  
        } //1*1的单独处理  
        if(num[1])  
                ans+=(num[1]%36) (num[1]/36+1):(num[1]/36);  
        printf("%d\n",ans);  
    }  
  
   return 0;  
}

解题思路二：

首先6*6,5*5,4*4的一次只能放一个，这样有多少个，就要用多少个包装袋，3*3的最多可以放4个，所以需要(num[3]+3)/4个包装袋，然后统计出空余部分2*2的个数。显然当放4*4时空出5个2*2，放3个3*3时，空出1个2*2；放2个3*3时，空出3个2*2；放1个3*3时，空出5个2*2；然后将2*2的全部搞定。最后用总的空间减去已放的空间就可以得到剩余的1*1的空间。

a/b的向上取整可以写为(a+(b-1))/b.

代码：

#include  
int main()  
{  
    int n,a,b,c,d,e,f,x,y;  
    int u[4]={0,5,3,1}; //当放i个3*3时，空出来的2*2的个数  
  
    while(1)  
    {  
        scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);  
        if(a==0&&b==0&&c==0&&d==0&&e==0&&f==0)  
            break;  
        n=d+e+f+(c+3)/4;//必须要这么多个包装袋  
        y=5*d+u[c%4];//在已有n个的情况下，能装下y个2*2的  
        if(b>y)  
            n+=(b-y+8)/9;//把多的2*2的弄进来  
        x=36*n-36*f-25*e-16*d-9*c-4*b;  
        if(a>x)  
            n+=(a-x+35)/36;//把1*1的弄进来  
        printf("%d\n",n);  
    }  
    return 0;  
}