这是一个创建于 3783 天前的主题，其中的信息可能已经有所发展或是发生改变。
输入三个数：巧克力的长和宽。和分割几刀。
输出最小块的最大值。
每份的长和宽都必须是整数。
比如6*7的巧克力割5刀，则把6均分为6份满足要求。输出7
请问怎么做？
输出最小块的最大值。
每份的长和宽都必须是整数。
比如6*7的巧克力割5刀，则把6均分为6份满足要求。输出7
请问怎么做？
 |
1
mthli 2014-07-25 14:29:22 +08:00  1
这个问题有一个简单的思路，不知道可不可行。
我们假设输入的长和宽分别为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。 |
 |
4
rrfeng 2014-07-25 16:15:33 +08:00
难道不是 1×1……
两刀切下一个角来 适用于 m>=2 的情况…… 没说要均分啊，比如 6 7 5 ，为什么不切成 16 16 16 16 16 26 ？ |
 |
6
regmach 2014-07-25 16:43:14 +08:00
题意不明吧?
"最小块的最大值"是说使最小的一块尽量最大吗? |
 |
8
latyas 2014-07-25 17:21:39 +08:00
切掉的部分还能再参与下一刀的切割吗？ 或者说是否支持十字型的切割
|
 |
10
flyee 2014-07-25 17:32:15 +08:00 1
def cut(a, b, m):
"""切到底＋最小值最大"""" return max([(a//(r+1))*(b//(m-r+1)) for r in range(m+1)]) |
|
11
regmach 2014-07-25 18:29:12 +08:00 1
// 设定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); |
 |
12
yangkeao OP |
|
13
latyas 2014-07-26 00:51:49 +08:00
TAT LZ这题目描述和segmentfault上完全不一样啊
|
 |
14
aheadlead 2014-07-26 08:13:01 +08:00
写个DP就好了 f(i,j,k)代表给一个ixj大的矩阵切k刀得到最大的面积
剩下的记忆化搜索就好了嘛 |
|
18
latyas 2014-07-26 10:10:36 +08:00 1
|
Select Language