贺州学院ivy


私信TA

用户名:Livy

访问量:1400

签 名:

好好学习,天天向上,汝何秀?

排  名 25
经  验 5383
参赛次数 4
文章发表 25
年  龄 0
在职情况
学  校 贺州学院
专  业 软件工程

  自我简介:

假猪套天下第一

解题思路:

}]2`CQ`8GK0}_RQ@{TP(`@G.png

 

 

 

根据图片,我们可以看到,我们要做的是铺平每一个箱子,也就是一个箱子只能有一层物品,因为他们高度都一样是h

1.  6*6的一个占满一个箱子

 

 

 

 

 

2.  5*5的不能同时放两个5*5,所以也只好一个占一个箱子,空余的空间,我们看到只能用1*1来填补,这里面放不了2*2的呀,箱子是6*6的箱子,而且只能放一层,高度大家都一样是h,注意了,可以放11个1*1来填满





3.  4*4的也是不能放两个自己,可以看到4*4的剩下的20空间,就可以用2*2和1*1来填满了,但是剩下20刚好是5个2*2填满了,就没必要用1*1了吧?除非是2*2不够的情况下,才用1*1来填满,也就是说,2*2数量满足的情况下,不需要1*1,不够才需要1*1.

 

 

 

 

 

4.  3*3可以看到,放4个自己的3*3就刚好放满了对吧?可以看到,3*3可以放自己1-4个都可以,所以,需要对3*3进行特殊处理:

A. 当只有1个3*3的时候---只有一个三3*3,剩下的27空间就只能用2*2和1*1来填满了。可以看到,在一个3*3情况,我们的2*2只能最多放5个2*2。如下图所示:就可以看到只能放5个2*2和7个1*1对吧?

                                  6SU[])59PHBRQOXK@})2YJ8.png                   

 


 

B.  当只有2个3*3的时候,剩下18的空间同样用2*2和11来填满,如下图所示:只能用3个2*2和6个1*1了

                                    KM[SY`@TR{8U1`4MUF0_P8G.png                   

 

 




C.  当只有3个3*3的时候,剩下9的空间,同样2*2和1*1填满,如下图所示:只能用1个2*2和5个1*1了

                                )W9BRE`(Y3VB_TYGH2_P1C9.png                         




D .4个3*3的时候就不需要了,刚好满

 



好,现在经过6*6-3*3后,我们就可以看看当目前为止可以用多少个箱子装6*6-3*3

可以看到6*6,5*5,4*4都是一个用一个箱子装,然后是3*3的,满四个装一个箱子,当3*3<=3的时候也要用一个箱子装,3*3>4,就例如5个时候,要用两个了对吧,所以我们需要对3*3进行判断需要多少个箱子

也就是3*3的箱子数 = (3*3个数+3)/4


这里解释为什么要+3,假设有3个3*3,但是也要用一个箱子装,有1*个3*3也是需要一个箱子装,有2个3*3也是需要一个箱子装,也就是说 +3 是为了让它能满足4的倍数

数学计算: (1+3)/4 = 1; (2+3)/4 = 1; (3+3)/4 = 1; (4+3)/4=1;

                    (5+3)/4=2;   (6+3)/4=2;  (7+3)/4=2;     (8+3)/4 = 2;

看完应该都可以理解了为什么+3了吧?

当然,你也可以不这样做,就判断(3*3个数%4==0)是否等于0

==0就箱子数=3*3个数/4。

!=0的时候,箱子数 = 3*3个数/4+1



好,到现在就可以确定当前要的箱子数: box = d+e+f+(c+3)/4;



好,确定完6*6-3*3的,那么就剩下了2*2和1*1怎样处理了。

先处理2*2,我们可以看到,需要用到2*2的地方,只有4*4和3*3对吧?那么我们可以这样子想,我们就计算需要填满4*4和3*3一共需要多少个2*2,

如果需要的2*2个数>=现实中有的2*2个数,就是不需要多开箱子,填完2*2后还剩下的空间用1*1来填。

box+=0;


如果需要的2*2个数<现实中有的2*2个数,就是说明,填满2*2后,还有剩下2*2,那么我们就需要为多出来的2*2来多加箱子来装了对吧?

思路了解后,那么我们就要来计算,一共需要多少个2*2的个数了吧,我们用变量need2num表示

我们上面知道了,一个4*4需要5个2*2,但是对于3*3的需要2*2个数是根据3*3的个数来确定的

剩下4个3*3,需要0个2*2和0个1*1

剩下1个3*3,需要5个2*2和7个1*1

剩下2个3*3,需要3个2*2和6个1*1

剩下3个3*3,需要1个2*2和5个1*1

我们用一个数组来存放对于3*3所需要2*2的个数           int need2[4] = { 0, 5, 3, 1 };

所以           need2num = d * 5 + need2[c % 4];

这样子就求出了需要用到的2*2个数了。


得出需要2*2个数后,就可以判断需不需要加箱子了

    if (need2num >= b){ box += 0; } //2*2的箱子刚好符合或者小于需要的,就不需要在开辟box箱子了


    else box += ((b - need2num) + 8) / 9; //这里是多出来的2*2的情况,需要加box箱子,加box箱子的数目需要看多出来几个,每多出9个就多加一个box箱子,这里的+8和上面+3的想法是一模一样的


 


接下来,可能就想到了,用同样的方法处理1*1对吧?但是告诉你这样子想是错误的,这样子想是根据2*2可以填满的情况下,但是当2*2不够,填不满4*4和3*3需要的2*2时候,我们就需要把剩下的所有空间用1*1来填了

,很明显这样的方法不能同样处理1*1




但是我们可以根据当前箱子的总数来判断1*1的所需,

  need1num = box * 36 - (f * 36 + e * 25 + d * 16 + c * 9 + b * 4);
  if (need1num >= a){ box += 0; }
  else box += ((a - need1num) + 35) / 36;

当前箱子数*36就是总的空间,减去6*6--2*2的所有空间,剩下的就是1*1的空间了嘛,然后根据需求数量和现实1*1的的数量判断是不是要加箱子



注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<functional>
#include<map>
#include<iomanip>
using namespace std;
int main(){
                int need2[4] = { 0, 5, 3, 1 };
                int a, b, c, d, e, f;
                while (cin >> a >> b >> c >> d >> e >> f){
                                if (a + b + c + d + e + f == 0)break;
                                int need2num = 0;
                                int need1num = 0;
                                int box = 0;
                                box = f + e + d + (c + 3) / 4;//6*6至到3*3首先要用了多少个box箱子
                                need2num = d * 5 + need2[c % 4];//到目前为止填满d和c一共需要的2*2的箱子数
                                if (need2num >= b){ box += 0; } //2*2的箱子刚好符合或者小于需要的,就不需要在开辟box箱子了
                                else box += ((b - need2num) + 8) / 9; //这里是多出来的2*2的情况,需要加box箱子,加box箱子的数目需要看多出来几个,每多出9个就多加一个box箱子
                                need1num = box * 36 - (f * 36 + e * 25 + d * 16 + c * 9 + b * 4);
                                if (need1num >= a){ box += 0; }
                                else box += ((a - need1num) + 35) / 36;
                                cout << box << endl;
                }
                return 0;
}
    

  评论区

给您跪了
2018-11-09 21:23:23 | |
  • «
  • 1
  • »