喵哈喽～！各位同学，今天由我，你们的小助教猫娘，来为大家讲解这道有趣的思维题哦 (ฅ'ω'ฅ) 这道题要求我们“最小化最大值”，一看到这种字眼，是不是有种熟悉的感觉扑面而来呢？嘿嘿，这可是二分答案的经典应用场景哦。 跟紧我的思路，我们一起来把它轻松解决掉吧！

D. Place of the Olympiad

---

题目大意喵

这道题是说呀，有一个 n 行 m 列的超——大考场，要安排 k 个同学进去考试，喵~。

在同一行里，如果几个同学的座位是连在一起的，我们就把这组座位叫做一个“长凳”(bench)。我们的任务就是，设计一个座位安排方案，让所有“长凳”里最长的那一个，它的长度尽可能地短。

最后，我们只要告诉裁判这个“最短的最长长凳长度”是多少就好啦。

举个栗子： 在 3 x 4 的场地里放 7 个同学。 如果第一行放 3 个，第二行放 2 个，第三行放两个单独的 1 个。那么长凳长度分别是 3, 2, 1, 1，最长的长凳是 3。 但我们可以安排得更好！比如每行最多放 2 个，这样最长的长凳长度就只有 2 啦。这就是我们要找的答案。

---

解题方法思路

一看到“最小化最大值”这种问题，我们聪明的脑袋瓜里就应该立刻闪过一道光——二分答案！

你想呀，假设我们规定最长的长凳长度不能超过 L。

• 如果这个 L 是可行的（我们能用长度不超过 L 的长凳放下所有 k 个同学），那么把限制放宽到 L+1 肯定也办得到，对吧？
• 反过来，如果连长度 L 的限制都无法满足，那更严格的 L-1 就更别想啦。

这种单调性就是二分答案最喜欢的朋友了，喵~

所以，我们可以对“最长长凳的长度”这个答案进行二分查找。答案的范围最小是 1（每个同学都单独坐），最大是 m（一行坐满了）。我们就在 [1, m] 这个区间里，去寻找那个最小的可行的 L。

二分的核心问题就变成了：

给定一个最大长凳长度 L，判断我们是否能放下至少 k 个同学？

---

详细题解 (ฅ'ω'ฅ)

为了判断一个给定的最大长凳长度 L 是否可行，我们当然要尽可能多地塞进同学啦！这里就要用到一点点贪心的思想。

对于每一行，要想放最多的桌子，就要用最少的空位把它们隔开。为了不让长凳的长度超过 L，我们每放 L 张桌子，就必须跟一个空位。就像这样：

桌桌...桌(L个) [空] 桌桌...桌(L个) [空] ...

这样一个 (L个桌子 + 1个空位) 的组合，总长度是 L+1。

在一行 m 个位置里，能放多少个这样的完整组合呢？很简单，就是 m / (L + 1) 个嘛。 所以，为了满足长度不超过 L 的限制，每一行至少需要 m / (L + 1) 个空位来做分割。

那么，这一行最多能放的桌子数就是： 总位置数 - 必须的空位数，也就是 m - m / (L + 1) 张桌子。

我们总共有 n 行，所以整个场地最多能放下的总桌子数就是： n * (m - m / (L + 1))

只要这个数量大于等于 k，就说明我们猜的 L 是可行的，我们就可以试试更小的 L (缩小二分范围到左半边)。如果不够，那就说明 L 太小啦，得猜个大一点的 (缩小二分范围到右半边)。喵~

把这个判断逻辑放进二分搜索的框架里，问题就迎刃而解啦！

下面是对应的代码实现，我已经加上了注释哦：

#include <iostream>

// 这个函数用来解决单个测试用例喵~
void solve() {
    long long n, m, k;
    std::cin >> n >> m >> k;

    // 二分查找最小的可能的最长长凳长度
    // 答案肯定在 [1, m] 之间
    long long low = 1, high = m;
    
    // 我们要找的是最小的 L，使得我们可以放下 k 张桌子
    while (low < high) {
        // 使用 low + (high - low) / 2 可以防止整数溢出哦
        long long mid = low + (high - low) / 2;

        // 计算如果最长长凳长度为 `mid`，一行最多能放多少桌子
        // 为了放最多桌子，我们就要用最少的空位
        // 每 `mid` 个桌子后需要一个空位，形成一个 `mid+1` 的块
        // 所以需要的空位数是 m / (mid + 1)
        // 最多桌子数 = 总位置数 - 必须的空位数
        long long desks_per_row = m - m / (mid + 1);

        // 计算整个场地能放下的总桌子数
        // n 和 desks_per_row 都可能很大，乘积会超过 int，所以要用 long long
        if (n * desks_per_row >= k) {
            // 如果能放下 k 张或更多桌子，说明 `mid` 是一个可行的答案
            // 我们尝试寻找一个更小（更好）的答案
            // 所以在 [low, mid] 区间里继续找
            high = mid;
        } else {
            // 如果放不下 k 张桌子，说明 `mid` 太小了
            // 我们需要一个更长的长凳
            // 所以在 [mid + 1, high] 区间里继续找
            low = mid + 1;
        }
    }

    // 当循环结束时，low == high，这就是我们找到的最小答案啦！
    std::cout << low << "\n";
}

int main() {
    // 加速输入输出，让程序跑得快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

相关知识点介绍

1. 答案二分 (Binary Search on the Answer)

这是一种非常常见的算法技巧，专门解决“求最小的最大值”或“求最大的最小值”这类最优化问题。

它的核心思想是把求解问题转换成判定问题。就像我们这道题，不是直接去计算那个最小长度，而是去猜一个长度 L，然后去判断“这个长度 L 可行吗？”。

只要这个“可行性”判断具有单调性（比如 L 可行，则所有大于 L 的都可行），我们就可以对答案的范围进行二分搜索，从而大大降低时间复杂度。

2. 贪心思想 (Greedy Approach)

在我们的 check 函数里，用到了贪心的思想。当我们需要判断在限制 L 下最多能放多少桌子时，我们的策略是“让每一行都尽可能地满”。

具体做法就是用最少的代价（一个空位）来满足限制（打断长凳），从而实现局部最优（每行放最多），并最终帮助我们判断全局情况。这就是贪心的魅力所在，喵~

---

好啦，这道题的讲解就到这里啦！是不是感觉二分答案和贪心思想的组合拳非常厉害呢？希望我的讲解能帮到你哦~ 如果还有不懂的地方，随时可以再来问我！下次见，喵~ (ฅ^•ﻌ•^ฅ)