VDON
  • 181

巧克力切割问题

【问题描述】
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
阅读 7.2k
评论 更新于 2014-07-25
    3 个回答

    一、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回来说一声,我再仔细想想

    评论 赞赏 2014-07-25

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

      评论 赞赏 2014-08-03
        inapt
        • 17

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

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

        这题是Codeforces原题。

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

        评论 赞赏 2014-07-30
          撰写回答

          登录后参与交流、获取后续更新提醒