巧克力切割问题

Question

【问题描述】Jzzhu有一块很大的巧克力，它由n × m个正方形小块组成。Jzzhu想要对巧克力进行k次切割。每次切割都满足如下规则：每次切割都必须是直的(横向或纵向)；每次切割都必须沿着正方形小块的边缘(不能切到里面)；每次都必须一切到底。想象Jzzhu进行了k次切割，巧克力被分成了几块。现在请考虑最小的那一块，Jzzhu希望这一块尽可能的大。那么在切割k次后这块最小的巧克力的大小的最大值是多少？巧克力的大小请以其所含的正方形小块的个数为基准。【输入】仅有一行，包含n, m, k【输出】输出共一行，包含一个整数，表示最小块的最大值。如果无法切割k次，输出-1。比如说6*7的巧克力分5刀，答案为7。【输入输出样例1】in642out8【输入输出样例2】in234out-1

Answer 1

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