题解 P7085 【[NWRRC2013]Garage】

CGDGAD · 2020-11-19 16:39:38 · 题解

作为这道题的首A，过来发一个题解，纪念一下。

题目大意

你有一个 W \times H 的大长方形。你又有无数个 w \times h 的小长方形。请问，最少放入几个小长方形后，你无法再往这个大长方形里放入其他的小长方形。

所有小长方形不能重叠，也不能旋转。

解题思路

一看就是一个数学题。

要让这个大长方形中不能再放入更多的小长方形，就是要把小长方形在大长方形中的分布越散越好。但垂直方向上的两个小长方形的距离必须小于 h，水平方向上的两个小长方形的距离必须小于 w，否则就放得下其他的小长方形了。

最后，我们的实现方式：

• 首先算出水平方向上（宽）最多能放几个长方形。
  • 此处的计算方法如代码中所示，应该能看得懂。
• 再计算出垂直方向上（高）最多能放几个长方形。

#include <cstdio>
#include <cmath>
int W, H, w, h;
int main() {
    scanf("%d%d%d%d", &W, &H, &w, &h);
    int a = (int)ceil( (double)(W - w + 0.000001) / (double)(2 * w - 0.000001) );
    int b = (int)ceil( (double)(H - h + 0.000001) / (double)(2 * h - 0.000001) );
    printf("%d\n", a * b);
    return 0;
}