P7892 『JROI-3』R.I.P.

· · 题解

Update

Content

你在一个无限大的格子平面上，并且有 m 个长度为 1 的栅栏，你需要用不多于 m 个栅栏围住一个面积恰好为 n 的区域，求是否可行。

如果你需要围住一个 a\times b 的区域，你需要用长为 a+1，宽为 b+1 的栅栏才能围住它。

数据范围：t 组数据，1\leqslant t\leqslant 10^3。1\leqslant n,m\leqslant 10^8。

Solution

首先引出我们小学就学过的东西：一个长方形在一定面积下，长与宽差得越小，周长也就越小。因此，我们由此想着求出一个长与宽差得最小的一个面积为 n 的区域。

我们先假设这个面积为 n 的区域是一个正方形，那么它的边长就是 \sqrt{n}，因此，我们不妨从 \lfloor\sqrt n\rfloor 开始向下枚举每一个可能的宽，如果枚举到了一个 \leqslant\lfloor\sqrt n\rfloor 的整数 x 使得 x\mid n，那么可以直接计算出最短周长为 2(x+\frac nx+2)，再拿这个东西和 m 比较就可以了。

Code

namespace Solution {
    ll n, m;

    iv Main() {
        MT {
            read(n, m);
            ll a, b;
            for(a = sqrt(n); a >= 1; --a) if(!(n % a)) break;
            b = n / a;
            ll mn = (a + b + 2) * 2;
            if(mn <= m) puts("Good");
            else puts("Miss");
        }
    }
}

Advertisement

欢迎来看我扒的 R.I.P. 的谱子！