题目描述

在一个 $n \times m$ 的矩形场地中安排 $k$ 名参赛者的座位。场地有 $n$ 行，每行有 $m$ 个座位点位。每个参赛者占据一个座位。

在一行中，如果多个连续的座位被占据，这组座位称为一个长凳，其长度是该组内座位的数量。

目标是安排这 $k$ 个座位的位置，使得所有行中最长长凳的长度尽可能小。你需要找出这个最小可能的最长长凳长度。

样例

输入 #1

5
3 4 7
5 5 5
1 13 2
2 4 7
1 5 4

输出 #1

2
1
1
4
2

样例 1 解释 (第一个测试用例):
n=3, m=4, k=7.
目标是安排 7 个座位，分布在 3 行，每行最多 4 个座位。要最小化最长连续座位数。
一种可能的安排是：
Row 1: O O _ O (最长 2)
Row 2: O O _ (最长 2)
Row 3: O O _ (最长 2)
总共 3 + 2 + 2 = 7 个座位。这种安排下，最长长凳长度是 2。
可以证明无法安排使得最长长凳长度为 1（因为要放 7 个人，平均每行超过 2 人，不可能只用长度 1 的长凳）。
所以最小的最长长凳长度是 2。

算法 1 (数学推导 O(1))

思路分析

1. 目标: 最小化所有行中长凳长度的最大值。设这个最小的最大长度为 $L$。

2. 单行容量: 考虑在一行（共 $m$ 个座位）中，如果我们要求最长的长凳长度不超过 $L$，最多可以放多少人？

   • 为了最大化人数，同时保证长凳长度不超过 $L$，最优策略是尽量放满 $L$ 个连续座位，然后空一个座位，再放 $L$ 个，再空一个，以此类推。即形成 O...O_O...O_ ... 的模式。
   • 一个完整的 “长凳+空位” 块的长度是 $L+1$。这个块里放了 $L$ 个人。
   • 在 $m$ 个座位中，最多可以放下 $b = \lfloor \frac{m}{L+1} \rfloor$ 个这样的完整块。这些块总共放了 $b \times L$ 个人。
   • 剩下 $rem = m \pmod{L+1}$ 个座位。在这些剩余的座位中，我们可以继续放人，但最多连续放 $L$ 个。由于 $rem < L+1$，即 $rem \le L$，我们可以在这剩下的 $rem$ 个座位上全都放人，而不会使得长凳长度超过 $L$。
   • 因此，在一行中，满足最长长凳长度不超过 $L$ 的条件下，最多可以放的人数 $t$ 为：
     $$t = b \times L + rem = \lfloor \frac{m}{L+1} \rfloor \times L + (m \pmod{L+1})$$
   • 这个公式还可以简化。注意到 $m = (L+1) \times \lfloor \frac{m}{L+1} \rfloor + (m \pmod{L+1})$。
     $$t = \lfloor \frac{m}{L+1} \rfloor \times L + m - (L+1) \times \lfloor \frac{m}{L+1} \rfloor$$
     $$t = m - \lfloor \frac{m}{L+1} \rfloor \times (L+1 - L) = m - \lfloor \frac{m}{L+1} \rfloor$$
     所以，单行的最大容量 $t = m - \lfloor \frac{m}{L+1} \rfloor$。

3. 总容量与需求:

   • 我们有 $n$ 行，每行最多放 $t$ 个人，总共最多可以放 $n \times t$ 个人，同时保证最长长凳长度不超过 $L$。
   • 我们需要安排 $k$ 个参赛者。为了使得目标 $L$ 可行，总容量必须大于等于 $k$：
     $$n \times t \ge k$$
     $$n \times (m - \lfloor \frac{m}{L+1} \rfloor) \ge k$$

4. 求解最小的 L:

   • 我们需要找到满足上述不等式的最小的非负整数 $L$。
   • 不等式可以变形为：
     $$m - \lfloor \frac{m}{L+1} \rfloor \ge \frac{k}{n}$$
   • 由于 $m - \lfloor \frac{m}{L+1} \rfloor$ 是整数，所以必须满足：
     $$m - \lfloor \frac{m}{L+1} \rfloor \ge \lceil \frac{k}{n} \rceil$$
   • 令 $k_{\text{avg}} = \lceil \frac{k}{n} \rceil$。这个值代表了为了放下 $k$ 个人，平均（向上取整）每行至少需要承担的人数。
   • 我们需要 $m - \lfloor \frac{m}{L+1} \rfloor \ge k_{\text{avg}}$。
   • 移项得到： $m - k_{\text{avg}} \ge \lfloor \frac{m}{L+1} \rfloor$。
   • 令 $E = m - k_{\text{avg}}$。$E$ 可以理解为：如果一行放了 $k_{\text{avg}}$ 个人，最多还剩下多少个空位。
   • 我们需要 $E \ge \lfloor \frac{m}{L+1} \rfloor$。
   • 根据下取整函数的性质，$\lfloor x \rfloor \le E$ 等价于 $x < E + 1$。
   • 所以，我们需要 $\frac{m}{L+1} < E + 1$。
   • $\frac{m}{E+1} < L+1$
   • $\frac{m}{E+1} - 1 < L$
   • 由于 $L$ 必须是整数，满足 $L > \frac{m}{E+1} - 1$ 的最小整数 $L$ 是 $\lfloor (\frac{m}{E+1} - 1) \rfloor + 1$ ？ 不完全对。
   • 我们从 $L+1 > \frac{m}{E+1}$ 出发。
   • $L+1 \ge \lfloor \frac{m}{E+1} \rfloor + 1$ （因为 $L+1$ 是整数）。
   • $L \ge \lfloor \frac{m}{E+1} \rfloor$。
   • 因此，满足条件的最小整数 $L$ 就是 $\lfloor \frac{m}{E+1} \rfloor$。
   • 代回 $E = m - k_{\text{avg}} = m - \lceil \frac{k}{n} \rceil$。
   • 最小的 $L = \lfloor \frac{m}{m - \lceil \frac{k}{n} \rceil + 1} \rfloor$。

5. 代码实现:

   • 计算 $k_{\text{avg}} = \lceil \frac{k}{n} \rceil$。在 C++ 中，可以使用 (k + n - 1) / n 来计算整数向上取整。
   • 计算 $E + 1 = m - k_{\text{avg}} + 1$。
   • 计算 $L = m / (E + 1)$ (整数除法，即下取整)。
   • 输出 $L$。

时间复杂度

该算法只涉及几次算术运算，时间复杂度为 $O(1)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// 使用 __int128 处理可能的大数乘积 (虽然本题 O(1) 解法不需要)
using i128 = __int128;
using u128 = unsigned __int128;

// 使用 C++20 的 ranges 和 views (虽然本题 O(1) 解法不需要)
namespace ranges = std::ranges;
namespace views = std::views;

// 处理单个测试用例的函数
void solve() {
    long long n, m, k; // 使用 long long 读入，因为 k 可能很大
    std::cin >> n >> m >> k;

    // 计算 k_avg = ceil(k / n)
    // (k + n - 1) / n 是整数向上取整的技巧
    long long k_avg = (k + n - 1) / n; 

    // 计算 E + 1 = m - k_avg + 1
    long long denom = m - k_avg + 1;

    // 计算 L = floor(m / (E + 1))
    // 注意：如果 denom <= 0 (即 m - k_avg + 1 <= 0, 或 m < k_avg),
    // 这意味着即使最长板凳是 m (即没有空位), 单行容量 m 也不足以承担 k_avg,
    // 这种情况理论上不应发生，因为 k <= n * m 保证了 k_avg <= m。
    // 但为安全起见，可以加检查。不过，根据推导，denom 必定 > 0。
    // 因为 k <= nm -> k/n <= m -> ceil(k/n) <= m -> k_avg <= m
    // -> m - k_avg >= 0 -> m - k_avg + 1 >= 1.
    long long ans = m / denom; // C++ 整数除法自动下取整

    std::cout << ans << "\n"; // 输出结果
}

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}

算法 2 (二分答案 O(log m))

思路分析

1. 二分答案: 我们要找的是最小的可能的最大长凳长度。设这个值为 $L$。我们可以发现答案具有单调性：如果允许的最大长凳长度为 $L$ 是可行的（即可以安排下 $k$ 个人），那么允许的最大长凳长度为 $L+1$ 也一定是可行的。反之，如果长度 $L$ 不可行，那么任何小于 $L$ 的长度也不可行。这表明我们可以对答案 $L$ 进行二分查找。

2. 二分范围: 最长长凳长度 $L$ 的可能范围是 $[0, m]$。（长度 0 对应 $k=0$，长度 $m$ 对应一行可以坐满）。

3. check(len) 函数: 我们需要一个函数 judge(len)（或 check(len)）来判断：是否可以将 $k$ 个人安排到 $n \times m$ 的座位上，使得最长长凳长度不超过 len？

   • 根据算法 1 的推导，我们知道在一行中，最长长凳长度不超过 len 的条件下，最多可以放 $t = m - \lfloor \frac{m}{\text{len}+1} \rfloor$ 个人。
   • 那么在 $n$ 行中，总共最多可以放 $n \times t$ 个人。
   • 所以，judge(len) 函数就检查 $n \times (m - \lfloor \frac{m}{\text{len}+1} \rfloor) \ge k$ 是否成立。如果成立，返回 true；否则返回 false。

4. 二分查找过程:

   • 设置查找区间的下界 st = 0，上界 en = m。
   • 当 st < en 时循环：
     • 计算中间值 md = st + (en - st) / 2 (避免溢出，且是下取整)。
     • 调用 judge(md)：
       • 如果 judge(md) 为 true，说明长度 md 是可行的，我们尝试更小的长度，所以将上界 en = md。
       • 如果 judge(md) 为 false，说明长度 md 太小了，不可行，我们需要增大长度，所以将下界 st = md + 1。
   • 循环结束后，st (或 en) 就是满足条件的最小长度 $L$。

时间复杂度

二分查找的范围是 $m$。每次 judge 函数的计算是 $O(1)$ 的。因此，总时间复杂度为 $O(\log m)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
// 定义 long long 别名
using i64 = long long; 
// 其他类型别名 (本题未使用)
// using u64 = unsigned long long;
// using u32 = unsigned;
// using i128 = __int128;
// using u128 = unsigned __int128;

// 处理单个测试用例的函数
void solve() {
    long long n, m, k; // 使用 long long 读入
    cin >> n >> m >> k;

    // judge(len) 函数：检查是否可以用长度不超过 len 的最长长凳安排 k 个人
    auto judge = [&](long long len) {
        // 计算单行在最大长度为 len 的限制下的容量 t
        // 防止 len+1 除零，但 len >= 0 保证 len+1 >= 1
        long long capacity_per_row = m - (m / (len + 1)); 
        // 计算 n 行的总容量
        long long total_capacity = n * capacity_per_row;
        // 判断总容量是否足够容纳 k 个人
        return k <= total_capacity; 
    };

    // 二分查找最小的可行长度 len
    long long st = 0, en = m; // 查找范围 [0, m]
    while(st < en) {
        // 计算中间值 md (向下取整)
        long long md = st + (en - st) / 2; 
        if(judge(md)) { 
            // 如果 md 可行，说明答案可能是 md 或者更小
            // 将上界缩小到 md
            en = md;
        } else {
            // 如果 md 不可行，说明答案必须大于 md
            // 将下界提升到 md + 1
            st = md + 1;
        }
    }
    // 循环结束时，st == en，即为最小的可行长度
    cout << st << endl; 
}

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}