前言

在回北京的火车上，今天就先解决一道简单的题吧=w=

第九题

题目

标题： 分巧克力 儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。 为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足： 1. 形状是正方形，边长是整数   2. 大小相同   例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？ 输入 第一行包含两个整数N和K。(1 <= N, K <= 100000)   以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)  输入保证每位小朋友至少能获得一块1x1的巧克力。    输出 输出切出的正方形巧克力最大可能的边长。 样例输入： 2 10   6 5   5 6   样例输出： 2 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗  < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 注意： main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include <xxx> 不能通过工程设置而省略常用头文件。 提交程序时，注意选择所期望的语言类型和编译器类型。

第一种做法

分析

首先题目保证每个小朋友可以分到1×1的巧克力。那么我们就慢慢扩大分割后每块巧克力的大小，看看这种大小的巧克力是否满足条件即可。

这样我们可以发现一个规律：如果某种大小的巧克力无法满足条件，那么所有比它大的巧克力都无法满足该条件。因为巧克力一定是越大，分出的块数更少的。

代码及运行结果

#include <cstdio> using namespace std; const int MAX_N = 1e5 + 5; long long h[MAX_N], w[MAX_N]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%lld%lld", &h[i], &w[i]); } int ans = 1; // 这里不需要longlong，因为答案不可能比原来的巧克力还要大 for (int i = 2; ; i++) { long long sum = 0; // 这个数可能会溢出int for (int j = 0; j < n; j++) { sum += (h[j] / i) * (w[j] / i); } if (sum < k) break; else ans++; } printf("%d\n", ans); return 0; }

运行结果：

第二种做法

分析

我们成功的完成了这道题并通过了样例。但是有一个问题，这个程序能否通过所有的样例呢？从正确性来讲是没有问题的，但是我们再次观察一下数据范围。

输入第一行包含两个整数N和K。(1 <= N, K <= 100000)  以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 

输入保证每位小朋友至少能获得一块1x1的巧克力。

我们回顾一下我们之前代码的核心部分。

for (int i = 2; ; i++) { long long sum = 0; // 这个数可能会溢出int for (int j = 0; j < n; j++) { sum += (h[j] / i) * (w[j] / i); } if (sum < k) break; else ans++; }

这段代码是一个二重循环，当每块巧克力的面积都很大，且块数很多的时候，我们会发现第二层循环将被多次执行。

怎样估计它的耗时呢？我们可以引进一个叫做时间复杂度的概念。它是一个多项式，表示耗时和哪些未知量相关。对于一个未知量，如果两个未知量可以合并成一个高次未知量，那么相对低次的就会被忽略。

关于时间复杂度的准确定义，可以参考《高等数学》之类的课本，也可以去看《算法导论》，里面会有详细的介绍。

对于这段代码来说，第一个循环取决于答案的大小，而答案的大小最大可以达到最大的h或w。这个值详细地来说，是每一块巧克力的h和w取最小值m，然后对所有的巧克力取m的最大值。而第二个循环取决于n，那么这段代码的时间复杂度就是O（mn）。

我们发现，m最大为1e5，也就是10^5，而n同样是1e5，那么这段代码可以跑到1e10次计算。

根据第七题我们所讲的，一段代码1s可以跑1e8次运算。而题目中有如下要求：

资源约定：峰值内存消耗（含虚拟机） < 256M

CPU消耗  < 1000ms

那么通过计算，我们很容易发现，这是不满足CPU消耗的（也就是时间消耗）。

所以我们现在需要想办法减少它的时间复杂度。

最简单的方法就是从现有的方法进行改进，那么是否可行呢？

从优化来讲，这两个循环都有优化的可能。我们就来分析一下：

第一重循环：循环的大小取决于答案的大小。如果我们能快速地确定答案的范围，这个循环的时间复杂度就会减小很多。

第二重循环：循环的大小取决于n的大小，似乎没办法优化，除非想出一种新的方法。

似乎只能优化第一重循环。。。怎样优化呢？

我们发现从小往大计算，会面对答案很大的情况，那么怎么确定答案的上界呢？

由于分割的巧克力块，最大最大也要满足总面积不超过当前巧克力块的总面积，所以我们通过巧克力的总面积估计出理论上可以分出的最大巧克力块的大小。

那么我们获得上界之后，怎么才能保证答案很大或答案很小都不会超时呢？我们同时地从两头进行计算即可。

代码及运行结果

#include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int MAX_N = 1e5 + 5; const double EPS = 1e-8; // 在浮点数运算中，会出现误差，EPS用于修正这些误差 long long h[MAX_N], w[MAX_N]; int main() {     int n, k, max_R = 0;     long long area = 0; //在每块巧克力都最大且数量也最大的情况下，area是1e18，并不会溢出     scanf("%d%d", &n, &k);     for (int i = 0; i < n; i++) {         scanf("%lld%lld", &h[i], &w[i]);         area += h[i] * w[i];         max_R = max(max_R, (int)min(h[i], w[i]));     }     int ans, L = 2, R = min(int(sqrt(area / k + EPS) + EPS), max_R);     while (true) {         long long sum = 0;         for (int j = 0; j < n; j++) {             sum += (h[j] / L) * (w[j] / L);         }         if (sum < k) {             ans = L - 1;             break;         }         else L++;         sum = 0;         for (int j = 0; j < n; j++) {             sum += (h[j] / R) * (w[j] / R);         }         if (sum >= k) {             ans = R;             break;         }         else R--;     }     printf("%d\n", ans);     return 0; }

运行结果：

第三种方法

分析

这样的解法能不能完美的解决这道题呢？实际上并不是。因为可能会有一种情况：答案很大，但是离上界又相距甚远。尽管这种情况很少见，但依然存在。

那么我们应该怎样继续优化呢？

暂时没有了= =。。。

那我们能不能找到一种新的方法解决这道题呢？

考虑之前发现的规律：在某一个大小的巧克力块不满足时，比它大的情况都不需要考虑；在某一个大小的巧克力块满足时，比它小的情况都不需要考虑。

为什么呢？因为巧克力块的大小越大，可以被分割出的块数就越少。

我们在确定答案的时候就可以利用这个规律：

我们在答案的范围中，寻找它的中间值。如果中间值符合条件，那么答案就肯定在中间值和上界之间，反之就在下界和中间值之间。

显然，这样找到答案，会节省很多时间，相比于之前的两重循环，这种方法只需要O（nlogn）的时间。在任何情况下，这种方法都是可行的。

实际上，这种方法有统一的算法名称：整数二分。在一个符合单调性的整数序列中找一个值，都可以用整数二分来完成。

代码及运行结果

#include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int MAX_N = 1e5 + 5; const double EPS = 1e-8; // 在浮点数运算中，会出现误差，EPS用于修正这些误差 long long h[MAX_N], w[MAX_N]; int n, k; bool judge(int x) { long long sum = 0; for (int i = 0; i < n; i++) { sum += (h[i] / x) * (w[i] / x); } return sum >= k; } // 以下这段代码被称为整数二分 int erfen(int L, int R) { int ans = L; while (L <= R) { int M = (L + R) / 2; if (judge(M)) { ans = M; L = M + 1; } else R = M - 1; } return ans; } int main() { int max_R = 0; long long area = 0; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%lld%lld", &h[i], &w[i]); area += h[i] * w[i]; max_R = max(max_R, (int)min(h[i], w[i])); } int ans = erfen(2, min(int(sqrt(area / k + EPS) + EPS), max_R)); printf("%d\n", ans); return 0; }

运行结果：

这样我们就完美解决这道题啦。

关于整数二分和浮点数精度修正，我们会在以后的博客中讲到=w=