题解：最小棋盘边长问题

题目分析

问题核心

给定红棋数量 a 和蓝棋数量 b，需要找到最小的 n，使得 n×n 棋盘能满足：

1. 摆放 a 个红棋和 b 个蓝棋；
2. 任意两个同色棋子上下左右不相邻；
3. 棋盘可留空。

关键结论

要满足摆放条件，需同时满足两个核心约束：

1. 总容量约束：n² ≥ a + b（棋盘总格子数需能放下所有棋子）；
2. 单颜色约束：ceil(n²/2) ≥ max(a, b)（棋盘最多能放的同色棋子数为棋盘格子数的一半向上取整，需能放下数量更多的那种颜色）。

算法思路

核心思路

采用二分查找寻找最小的 n：

1. 确定二分查找的范围：左边界 l=0，右边界 r=2e5（足够覆盖 1e9 级别的棋子数，因为 (2e5)²=4e10 ≥ 2×1e9）；
2. 对每个中间值 mid，检查是否满足两个核心约束；
3. 若满足，尝试缩小右边界寻找更小的 n；若不满足，扩大左边界。

约束检查逻辑

对于候选边长 mid：

• 总容量：mid × mid ≥ a + b；
• 单颜色最大容量：ceil(1.0 × mid × mid / 2) ≥ max(a, b)（用浮点运算实现向上取整）。

代码

void solve() {
    cin >> n >> m;
    l = 0, r = 2e5;
    int r1 = 2e5;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (mid * mid >= n + m && ceil(1.0 * mid * mid / 2) >= max(n, m)) {
            r1 = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << r1 << endl;
}

复杂度分析

• 时间复杂度：每组测试数据二分查找的次数为 O(log(2e5)) ≈ 18，总复杂度为 O(T×log(2e5))，可轻松处理 T=1e5 的情况；
• 空间复杂度：O(1)，仅使用常数级额外空间。