巧克力分割问题 我校模拟赛题

[yangkeao]

输入三个数：巧克力的长和宽。和分割几刀。
输出最小块的最大值。
每份的长和宽都必须是整数。

比如6*7的巧克力割5刀，则把6均分为6份满足要求。输出7
请问怎么做？

[mthli]

这个问题有一个简单的思路，不知道可不可行。

我们假设输入的长和宽分别为a和b，而要求切m刀（也就是要求分成m + 1块）。

情况一：
如果a * b / (m + 1) 得到的恰好是一个整数n，也就是说，m刀的情况下恰好能均分，那么这个整数n就是最小块的最大值。

情况二：
如果a * b / (m + 1)得到的不是一个整数呢？
我们可以先计算 a * b / m，得到一个整数p和一个余数q。也就是说，此时可以分得m + 1块，前m块每一块含有面积p，而 最后一块含有面积q。
为了方便解释，我给前面m块进行编号好了，分别是M1，M2，M3, ... , Mm。
现在我们从Mm开始进行如下操作：
1. 从Mm的面积p中减1，把这个1累加到q上。比较此时的q值与Mm的p值大小，如果q < p，则进行2操作；如果q >= p，则说明此时q已经是最大值。
2. 从M(m - 1)的面积p中减1，把这个1累加到q上。比较此时的q值与M(m - 1)的p值的大小，如果q < p，则进行3操作；如果此时q >= p，则说明此时q已经是最大值。
3. 如上1、2两部操作所述，从M(m - 2) -> M1方向一直进行类似的p减1与q加1，然后比较q值和对应的p值。如果q < p，则继续；否则说明此时q已经是最大值。如果在3中仍然没有找到q的最大值，则进行4操作。
4. 从Mm重新开始新一轮的循环计算与比较。也就是回到1操作重新开始。
我想，根据以上4步，最后应该能够得到最小块的最大值。

打个比方，现在a = 3，b = 7，要求切m = 5刀（也就是要求分为6块）。
现在3 * 7 / 6 != 整数，所以我们3 * 7 / 5 = 4 余 1，根据上面四步走下来，最后可以得到最小块的q值应该是4。

[mthli]

@mthli 啊呀最后那个例子举措了，应该是要求m = 4（也就是要求分为5），最后的答案才是q = 4。

[yangkeao]

@mthli 可是答案应该是3。。我用没有优化的程序暴力跑得。

数据很大，暴力不行

[rrfeng]

难道不是 1×1……
两刀切下一个角来
适用于 m>=2 的情况……


没说要均分啊，比如 6 7 5 ，为什么不切成 16 16 16 16 16 26 ？

[yangkeao]

@rrfeng 一切要切到底。。。。。

[regmach]

题意不明吧?
"最小块的最大值"是说使最小的一块尽量最大吗?

[yangkeao]

@regmach 嗯，是的

[latyas]

切掉的部分还能再参与下一刀的切割吗？ 或者说是否支持十字型的切割

[rrfeng]

@yangkeao
嗯，我理解也有问题。
十字切割也是疑问！

[flyee]

def cut(a, b, m):
"""切到底＋最小值最大""""
return max([(a//(r+1))*(b//(m-r+1)) for r in range(m+1)])

[regmach]

// 设定a_min为辅助, b_max为主C
a_min = min(a, b);
b_max = max(a, b);

// 让辅助承受更多伤害, 剩余伤害由主C承受
// m1,m2为辅助和主C承受的伤害, (m1 - 1) + (m2 - 1) = m;
m1 = min(a, m+1);
m2 = m - m1 + 2;

// 计算团队整体收益
squ = floor(a_min, m1) * floor(b_max, m2);

[yangkeao]

@regmach
@flyee
@rrfeng
@latyas
@mthli
感谢大家辛苦的思考。

问题已经在segmentfault上的得到了答案。

http://segmentfault.com/q/1010000000617585

谢谢大家

[latyas]

TAT LZ这题目描述和segmentfault上完全不一样啊

[aheadlead]

写个DP就好了 f(i,j,k)代表给一个ixj大的矩阵切k刀得到最大的面积
剩下的记忆化搜索就好了嘛

[aheadlead]

@yangkeao 你要把数据范围拿上来啊...

[yangkeao]

@latyas 抱歉，那就是我的描述问题。
segmentfault上我是复制的题目，更加准确。

谢谢

[yangkeao]

@aheadlead n<100000 m<100000 k<200000

[latyas]

@yangkeao 有几个关键部分 V2EX上没写, 题目难度就瞬间变得很大.

1. 每次切割是纵向或者横向
2. 每次切割都必须沿着正方形小块的边缘

我以为是任意切割并且允许十字切割

[yangkeao]

@latyas 哦，抱歉