【搜狐】笔试算法题

假设包裹大小n*n表示为（n,n） 所有的尺寸（1，1），（2，2），----（k,k） k<=n 将（i,i）大小的包裹放进（n-i+i）^2 = (n-i)^2 + 2*(n-i)*(i) + i^2 所以空间变成了（n-i,n-i） (n-i,i) (n-i,i) (i,i) 其中感觉(n-i,n-i) (i,i)可以直接用这种尺寸的包裹填充 至于（n-i,i）举个例子（10，4）那么就形成了（4,4）(6,4)然后（4，4），（4，4）（2，4）然后（4,4）(4,4)(2,2)(2,2)相当于划分至平方数的形式 i从要装的大的包裹开始，容易算一些 能想到的思路，，，， 感觉好难。。。。。。(不确保完全正确) 感觉如果真要写出来有点像dp了 跟之前阿里那个立方体包裹题神似啊。。。

正解就是Lz最后括号里的那句话吧，“一个个讨论，因为6*6也不怎么大，要是商品规格一变，容器大小一变就没法做了”，直接硬算就好了，O(1)的复杂度。 这题就是巧在6能被1，2，3整除，从而保证贪心策略是正确的。

额、、感觉6能被1，2，3整除，从而保证贪心策略是正确的。还是挺难证明的哎。。 讨论6*6和5*5都是确定的。然后讨论4就感觉。。。能不能多讲一点[ema11] 【 在 caesar11 的大作中提到: 】 : 正解就是Lz最后括号里的那句话吧，“一个个讨论，因为6*6也不怎么大，要是商品规格一变，容器大小一变就没法做了”，直接硬算就好了，O(1)的复杂度。 : 这题就是巧在6能被1，2，3整除，从而保证贪心策略是正确的。

4的情况：每个箱子只能装下一个4*4，剩下的空间可以装5个2*2或20个1*1。这里贪心的策略是，装4*4的箱子的剩下的空间，先紧着2*2的装，如果还有剩的空间话再装1*1。 至于贪心策略的正确性证明一般是以下“套路”：假设存在一个不符合该贪心策略的“最优”解，然后从“最优”解出发，通过调整，转换到一个“同优”的且符合该贪心策略的解。 把“套路”套在这个问题上：显然，最优解和贪心解装有4*4的箱子数量一定是相等的。假设最优解比贪心解在装有4*4的箱子的剩余空间中，少装了x个2*2。那么在最优解中：（1）装4*4地箱子中，这x的部分，要么是空着的，要不然装了0～4x的1*1；（2）然后x个2*2必须在其他箱子里装着。这样一来，把（1）和（2）置换，不需要增加新的箱子，而置换后的策略就是贪心得到的策略。因此，贪心是正确的。 【 在 w350053002 的大作中提到: 】 : 额、、感觉6能被1，2，3整除，从而保证贪心策略是正确的。还是挺难证明的哎。。 : 讨论6*6和5*5都是确定的。然后讨论4就感觉。。。能不能多讲一点[ema11] : 【 在 caesar11 的大 : ......... 发自「贵邮」

可以的！！这个贪心证明算是很讲道理了。谢谢啦[ema23] 【 在 caesar11 的大作中提到: 】 : 4的情况：每个箱子只能装下一个4*4，剩下的空间可以装5个2*2或20个1*1。这里贪心的策略是，装4*4的箱子的剩下的空间，先紧着2*2的装，如果还有剩的空间话再装1*1。 : 至于贪心策略的正确性证明一般是以下“套路”：假设存在一个不符合该贪心策略的“最优”解，然后从“最优”解出发，通过调整，转换到一个“同优”的且符合该贪心策略的解。 : 把“套路”套在这个问题上：显然，最优解和贪心解装有4*4的箱子数量一定是相等的。假设最优解比贪心解在装有4*4的箱子的剩余空间中，少装了x个2*2。那么在最优解中：（1）装4*4地箱子中，这x的部分，要么是空着的，要不然装了0～4x的1*1；（2）然后x个2*2必须在其他箱子里装着。这样一来，把（1）和（2）置换，不需要增加新的箱子，而置换后的策略就是贪心得到的策略。因此，贪心是正确的。 : ...................

bf求后续 【 在 a940100079 (一笑一蹙) 的大作中提到: 】 : 假设包裹大小n*n表示为（n,n） : 所有的尺寸（1，1），（2，2），----（k,k） k<=n : 将（i,i）大小的包裹放进（n-i+i）^2 = (n-i)^2 + 2*(n-i)*(i) + i^2 所以空间变成了（n-i,n-i） (n-i,i) (n-i,i) (i,i) : ...................

没记错的话，这个好像是lc上的题。。。 【 在 liuyehcf (安静的牛皮糖) 的大作中提到: 】 : 题目： : 工厂生产的产品包装在相同高度h，尺寸为1*1,2*2,3*3,4*4,5*5,6*6的方形包装中。这些产品始终以与产品高度相同的尺寸为6*6的包裹交付给用户。因为邮费很贵，所以工厂要想方设法减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省运费 : ...................

【 在 liuyehcf 的大作中提到: 】 : 题目： : 工厂生产的产品包装在相同高度h，尺寸为1*1,2*2,3*3,4*4,5*5,6*6的方形包装中。这些产品始终以与产品高度相同的尺寸为6*6的包裹交付给用户。因为邮费很贵，所以工厂要想方设法减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省运费 : 输入描述：输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开。分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾 : ................... 楼主你看我的这个方法行不行。 这个题只需要讨论3×3，2×2就可以了吧。 6*6，5*5，4*4肯定是每一个都要装一个箱子： 设输入n1,n2,n3,n4,n5,n6 那么总数count+=n4+n5+n6 剩下的空隙中，定义fillWithOne,fillWithTwo; 这样fillWiteOne=n5*(6*6-5*5); fillWithTwo=n4*(6*6-4*4)/4; 这样只能填充1×1和能够填充2×2的就算出来了。 然后3*3比较特殊，需要特别讨论 首先count+=n3/4; 然后看n3%4； 分别讨论余数，看fillWithOne,fillWithTwo分别能加多少（这个画图可以很直观）。 接着只能填充1×1，能够填充2×2的就分别算出来了。这样分别吧2×2，1×1的填进去。 接着再讨论一下2×2，1×1的剩余情况就好了。 如果没有剩余，就算出来了。 如果2×2有剩余，1×1没有剩余，算下就好了。 同理1×1有剩余，2×2没有剩余。 1×1，2×2都有剩余（这时候讨论就很简单了。）。