北大ACM——Packets（贪心）贪心

【北大ACM——Packets（贪心）】题意：有一堆等高的包装好的产品，有1×1，2×2，3×3，4×4，5×5，6×6六种包装，且有6×6的包裹，用来装这些包装好的产品。分别给出每种包装的数量，求所需的最少的包裹。
分析：一个包裹只能容下1个6×6余0空位，1个5×5余11，1个4×4余20，最多能容下4个3×3，9个2×2，36个1×1。
贪心策略：尽可能地利用空间。先从大的装起，6×6的独用一个，其它的若有剩余，则用1×1或2×2去填补空间，需要注意，5×5只能用1×1去填补剩余空间。
伪代码如下：
long long a1,a2,a3,a4,a5,a6;
long long lef2,lef3,lef4,lef5;
long long sum;
while(~scanf("%lld"a1-a6))
{
lef2=lef3=lef4=lef5=sum=0;
sum=a4+a5+a6;
lef5=a5×(36-25); lef4=a4×(36-16);
if（5×5有剩余）{用1×1填补，a1减少且不得小于0}
if（4×4有剩余）{先用2×2填补，a2减少且不得小于0，若仍有剩余，再用1×1填补，a1减少}
if（3×3没有剩余）{sum+=a3/4}
else {sum+=a3/4+1; a3%4; lef3=36-9×a3; }
if（lef327）{分别用2×2,1×1去填补}
else if（lef318） {…}
else if（lef3==9） {…}
if（a2!=0）
{if（a2没有剩余）{sum+=a2/9; a2=0}
else{sum+=a2/9+1; a2%=9; lef2=36-4×a2; 用1×1去填补}
}
if（a1!=0）
{
if（a1没有剩余）{sum+=a1/36; a1=0; }
else {sum+=a1/36+1; a1=0; }
}
输出sum；
}
代码如下：

#include using namespace std; int main() { long long a1,a2,a3,a4,a5,a6; long long lef2,lef3,lef4,lef5; long long sum; while(~scanf("%lld %lld %lld %lld %lld %lld",&a1,&a2,&a3,&a4,&a5,&a6)&&(a1||a2||a3||a4||a5||a6)) { sum=lef2=lef3=lef4=lef5=0; sum=sum+a6+a5+a4; lef5=a5*(36-25); lef4=a4*(36-16); // printf("%lld %lld\n",lef4,lef5); if(a3%4==0) sum=sum+a3/4; else { sum=sum+a3/4+1; a3%=4; lef3=36-a3*9; } if(lef5!=0) { a1=a1-lef5; if(a1<0) a1=0; //每次使用都要使数量减少，且不得小于0； } if(lef4!=0) { if(a2*4>=lef4) { a2=a2-lef4/4; //printf("%lld a2\n",a2); 注意代码顺序，WA了一次就因为顺序搞错 lef4=0; } else { lef4=lef4-a2*4; a2=0; a1=a1-lef4; if(a1<0) a1=0; } } if(lef3!=0) { if(lef3==27) { if(a2>=5) { a2=a2-5; lef3=7; } else { lef3=lef3-a2*4; a2=0; } a1=a1-lef3; if(a1<0) a1=0; } else if(lef3==18) { if(a2>=3) { a2=a2-3; lef3=6; } else { lef3=lef3-a2*4; a2=0; } a1=a1-lef3; if(a1<0) a1=0; } else if(lef3==9) { if(a2>=1) { lef3=5; a2--; } a1=a1-lef3; if(a1<0) a1=0; } } if(a2!=0) { if(a2%9==0) { sum=sum+a2/9; a2=0; } else { sum=sum+a2/9+1; a2%=9; lef2=36-4*a2; a1=a1-lef2; if(a1<0) a1=0; } } if(a1!=0) { if(a1%36==0) sum=sum+a1/36; else sum=sum+a1/36+1; } printf("%lld\n",sum); } return 0; }

小结：分析仔细，从大的开始处理。不算难，但考验代码的能力。