巧克力切割问题

Question

【问题描述】
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

Answer 1

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

二、 min(m,n) <= k < max(m,n), 这里假设 m>n
计算 (m//(k+1))*n 和 m//(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回来说一声，我再仔细想想

Answer 2

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

Answer 3

使最小的最大，只有一种方法 —— 取平均值 。（思考一下为什么）

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

这题是Codeforces原题。

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