巧克力切割问题

Question

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

Answer 1

一、km+n-2out:-1注：//为整除思路大概就是：切k刀，即分k+1块，所以好的情况是均分（整除），所以有任何一边能被k+1整除，答案就出来的；但是如果min(m,n)m+n-2，这种就是下不了刀了，都切满了。PS：上面有个假设一定要先切完一边再切另一边，我是这样认为的，每多一刀，每块大小从1/k减少到1/(k+1），即1/(k+1)*k,即减少量递减，如果换到另外一边则k=1，则直接减少一半！上面假设没有严谨证明，可能是错误的，哈哈~PS：WA回来说一声，我再仔细想想

Answer 2

首先这个是Codeforces原题链接。div2c看了采纳的那个回答。感觉有点问题，因为涉及到的操作都是整除所以有时贪心是不对的。说另一个非贪心做法。原题中n,m