D. Place of the Olympiad 详细题解

一、问题重述

有一个 $n \times m$ 的矩形场地，要放置 $k$ 个桌位。桌位只能放在格子里，同一行中连续放置的桌位形成一条长凳。要求最小化最长长凳的长度。

例如，$n=3, m=4, k=7$ 时，最优安排是每行最多连续 $2$ 个桌位，答案为 $2$。

---

二、核心思路

2.1 函数定义

设最长长凳长度为 $x$。在一行中，如何安排才能容纳最多的桌位？

• 将每 $x+1$ 个位置视为一个块：前 $x$ 个位置放桌位（形成一个长凳），第 $x+1$ 个位置空出作为分隔。
• 每行可以放 $\left\lfloor \frac{m}{x+1} \right\rfloor$ 个完整的块，产生 $\left\lfloor \frac{m}{x+1} \right\rfloor \cdot x$ 个桌位。
• 最后剩余 $m \bmod (x+1)$ 个位置，可以再放 $\min(m \bmod (x+1), x)$ 个桌位（若余数小于等于 $x$ 则全放，否则不能超过 $x$，但余数肯定小于 $x+1$，所以当余数为 $x$ 时也可以放 $x$ 个）。

因此一行最多容纳的桌位数为：

$$f(x) = x \cdot \left\lfloor \frac{m}{x+1} \right\rfloor + \min\left(m \bmod (x+1),\; x\right) $$

实际余数部分就是 $m \bmod (x+1)$，因为余数 $< x+1$，且当余数等于 $x$ 时也可以放 $x$ 个。所以：

$$f(x) = x \cdot \left\lfloor \frac{m}{x+1} \right\rfloor + \left(m \bmod (x+1)\right) $$

2.2 可行性条件

由于 $n$ 行独立，总共最多可以放 $n \cdot f(x)$ 个桌位。要能容纳 $k$ 个桌位，需满足：

$$n \cdot f(x) \ge k$$

2.3 单调性

当 $x$ 增大时，$f(x)$ 也单调非减（允许更长的长凳，可以放更多桌位）。因此可以用二分查找最小的 $x$ 满足 $n \cdot f(x) \ge k$。

---

三、公式推导（可选）

对于给定 $x$，$f(x) = \left\lceil \frac{m}{x+1} \cdot x \right\rceil$ 的近似？不精确。更简单的：一行中最少需要的空位数为 $\left\lceil \frac{k}{n} \right\rceil$ 个桌位时，用二分找 $x$。

但标程使用二分查找，简洁有效。

---

四、标程代码

#include <iostream>
using namespace std;

void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    
    long long l = 0, r = m;  // 答案在 [1, m] 之间
    while (l + 1 < r) {
        long long mid = (l + r) / 2;
        // 计算当最大 bench 长度为 mid 时，一行最多能放多少个座位
        long long seats_per_row = (m / (mid + 1)) * mid + (m % (mid + 1));
        if (seats_per_row * n >= k) {
            r = mid;  // 可行，尝试更小的长度
        } else {
            l = mid;
        }
    }
    cout << r << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1：$n=3, m=4, k=7$

• 二分：
  • $mid=2$：每块长度 $3$（$2+1$），$\lfloor 4/3 \rfloor=1$ 块 → $1 \times 2 = 2$，余数 $4\%3=1$ → 可加 $1$，共 $3$ 个/行，$3 \times 3 = 9 \ge 7$ ✅ → $r=2$
  • $mid=1$：每块长度 $2$，$\lfloor 4/2 \rfloor=2$ 块 → $2 \times 1 = 2$，余数 $0$，共 $2$ 个/行，$3 \times 2 = 6 < 7$ ❌ → 最终 $r=2$ ✅

示例 2：$n=5, m=5, k=5$

• $mid=1$：每块长度 $2$，$\lfloor 5/2 \rfloor=2$ 块 → $2 \times 1=2$，余数 $1$ → 共 $3$ 个/行，$5\times 3=15\ge5$ ✅ → 继续缩小
• $mid=0$：每块长度 $1$，$\lfloor 5/1 \rfloor=5$ 块 → $5\times0=0$，余数 $0$，共 $0$ 个/行 ❌ → 答案为 $1$ ✅

示例 3：$n=1, m=13, k=2$

• 最长 bench 长度为 $1$ 时，一行最多放 $\lfloor 13/2 \rfloor \times 1 + (13\%2)=6+1=7 \ge 2$ ✅ → 答案为 $1$ ✅

---

六、复杂度分析

• 二分查找：$O(\log m)$
• 总复杂度：$O(t \log m)$，$t \le 10^4$，$m \le 10^9$，完全可行

---

七、总结

步骤	操作
1	二分答案 $x$（最长 bench 长度）
2	计算当 bench 长度为 $x$ 时，一行最多能放的座位数 $f(x)$
3	若 $n \cdot f(x) \ge k$，则 $x$ 可行，缩小右边界
4	否则增大左边界

核心公式：

$$f(x) = x \cdot \left\lfloor \frac{m}{x+1} \right\rfloor + \left(m \bmod (x+1)\right) $$

利用二分查找最小 $x$ 满足 $n \cdot f(x) \ge k$。