codeforces 450C. Jzzhu and Chocolate 解题报告(449A)

题目链接：http://codeforces.com/contest/450/problem/C

题目意思：给出一个 n * m 大小的chocolate bar，你需要在这个bar上切 k 刀，使得最小的部分面积尽可能大，求出这个被划分后的最小部分面积最大可以为多少。如果这个chocolate bar 不能切成 k 部分，则输出-1。注意，每一刀需要符合3个条件：1、打横切或者打竖切； 2、每一刀只能经过unit square（即1*1的单元bar）的边，也就是说不能把一个单元bar损坏，要完整； 3、每一刀只能在整个chocolate bar的里面操作，也就是说，外围的四条边是不允许切的。还有一个条件就是，每一刀都是不相同的。

我觉得自己做这道题目有点凭感觉的意味，所以可能读者会有点不赞同，欢迎指出 ^_^

首先要知道什么时候这个大bar不能切成 k 刀。很容易知道是如果k > (n-1)+(m-1) 的情况，因为外围的四条边是不允许操刀的！排除这个不能切的情况后，那么就要根据是从n（打横切）还是从m（打竖切）来进行讨论了。不过由于我们不能一眼看出哪种方案更优，所以两者都要讨论下，我一开始只想到 if 中的两条式子，n/(k+1)的意思表示这 k 刀都打横切，而分母为什么是k+1而不是k，是因为一刀可以把一个区域分成两部分，两刀就三个部分，依次类推。而我们需要求的是面积，就需要用到部分，而不是刀数了。m/(k+1)依此类推。

不过问题出现了，我根据test10返回的wa结果来想出的^_^。有可能完全打横切或者打竖切都没有切够k刀！那么就需要把剩余的刀数分到打竖切（对应之前完全打横切）或者打横切（对应之前的完全打竖切）中了。也就是代码中else的部分。其实完整的a1表达式是这样的：n/(n-1) * m/(k-(n-1)+1)，意思：完全打横切，只能切n-1刀，那么它划分的最小部分的面积就充当1了，至于m/(k-(n-1)+1) 表示打竖切还能切多少刀，+1是因为是求分成的部分，而不是多少刀，与if中的n/(k+1)中的+1意思是相同的。

（好开心这道题目排到最少用时的26名，继续努力！ ^_^）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 LL n, m, k;

 int main()

 {

     while (scanf("%lld%lld%lld", &n, &m, &k) != EOF)

     {

         if (k > n+m-)

             printf("-1\n");

         else

         {

             LL a1, a2;

             if (n > k+ || m > k+)

             {

                 a1 = n/(k+) * m;

                 a2 = m/(k+) * n;

             }

             else   // 针对test10的情况

             {

                 a1 = m/(k-(n-)+);

                 a2 = n/(k-(m-)+);

             }

             LL ans = max(a1, a2);

             printf("%lld\n", ans);

         }

     }

     return ;

 }

它的分类是贪心，但我觉得更像是数学，所以我就归到数学里吧。

巴特西

codeforces 450C. Jzzhu and Chocolate 解题报告(449A)

最新文章

热门文章