2

【问题描述】
Jzzhu 有一块很大的巧克力,它由 n × m个正方形小块组成。Jzzhu 想要对巧克力进行 k 次切割。每次切割都满足如下规则:

  1. 每次切割都必须是直的 (横向或纵向);
  2. 每次切割都必须沿着正方形小块的边缘(不能切到里面);
  3. 每次都必须一切到底。

想象 Jzzhu 进行了 k 次切割,巧克力被分成了几块。现在请考虑最小的那一块,Jzzhu 希望这一块尽可能的大。那么在切割k次后这块最小的巧克力的大小的最大值是多少?巧克力的大小请以其所含的正方形小块的个数为基准。

【输入】

仅有一行,包含 n, m, k

【输出】

输出共一行,包含一个整数,表示最小块的最大值。如果无法切割 k 次,输出 -1。
比如说 6*7 的巧克力分 5 刀,答案为 7。

【输入输出样例 1】

in
6 4 2  
out
8

【输入输出样例 2】

in
2 3 4  
out
-1
VDON 181
2014-07-25 提问
3 个回答
2

已采纳

一、k < min(m,n)
计算 (m//(k+1))*n(n//(k+1))*m,取较大者

二、 min(m,n) <= k < max(m,n), 这里假设 m>n
计算 (m//(k+1))*nm//(k-n+2),取较大者

三、 k >= max(m, n)
计算m//(k-n+2)n//(k-m+2), 较大者

四、 k > m+n-2
out: -1

注: // 为整除

思路大概就是:
切k刀,即分k+1块,所以好的情况是均分(整除),所以有任何一边能被k+1整除,答案就出来的;
但是如果min(m,n) <= k < max(m,n) 即小的一边够切,长边够切:那就分别考虑短边切完再切长边,和只切长边的情况;
如果k >= max(m, n),即长短边都不够切:那就分别考虑先长后短 和 先短后长的情况。
最后k > m+n-2,这种就是下不了刀了,都切满了。
PS:上面有个假设一定要先切完一边再切另一边,我是这样认为的,每多一刀,每块大小从1/k 减少到 1/(k+1),即1/(k+1)*k, 即减少量递减,如果换到另外一边则k=1,则直接减少一半! 上面假设没有严谨证明,可能是错误的,哈哈~

PS: WA回来说一声,我再仔细想想

1

首先这个是Codeforces原题链接。div2 c
看了采纳的那个回答。感觉有点问题,因为涉及到的操作都是整除所以有时贪心是不对的。
说另一个非贪心做法。
原题中n,m<=10^9显然O(n)的算法是过不去的。
(当时做那场cf的时候是bk大神告诉的做法。)
首先判无解。
有解时,然后我们要枚举切几刀,显然平均更优,但是这个枚举不能每个都枚举。
我们要求的是 [n/x]*[m/(k-x)]的最大值([]下取整)。
可以证明一个数n,整除它的结果最多只有2√n种取值。
然后就可以枚举[n/x]的取值。
就可以在O(√n)时间内解决。

0

使最小的最大,只有一种方法 —— 取平均值 。(思考一下为什么)

所以枚举纵向砍几刀,横向砍几刀。取最大值就可以了。

这题是Codeforces原题。

出题人如果不标出处的话,祝他内存泄露 :)

撰写答案

推广链接