题解 | #小红的矩阵#

核心思想：二分答案

1. 确定数值范围：矩阵中最小的元素是 ，最大的元素是 。我们要找的第 小的数一定在这个区间 内。
2. 单调性分析：如果我们选定一个数值 ，我们可以很容易地计算出矩阵中有多少个元素是小于等于 的。
   • 如果小于等于 的元素个数 ，说明第 小的数一定在 范围内（即 可能是答案，或者答案比 小）。
   • 如果小于等于 的元素个数 ，说明 太小了，第 小的数一定在 范围内。
3. 计数逻辑：对于给定的数值 ，如何快速计算矩阵中有多少个元素 ？
   • 矩阵第 行的元素为 。
   • 对于第 行，我们需要找到满足 的最大的 （其中 ）。
   • 不等式变形为 。
   • 同时受限于列数 ，第 行中小于等于 的元素个数为 。
   • 我们要做的就是遍历每一行，累加这个计数值。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, k;
    cin >> n >> m >> k;

    ll L = 1;
    ll R = n * m;
    ll ans = 0;

    auto check = [&](ll x) -> bool {
        ll cnt = 0;
        for (ll i = 1; i <= n; i++) {
            cnt += min(m, x / i);
        }
        return cnt >= k;
    };

    while (L <= R) {
        ll mid = L + (R - L) / 2;
        if (check(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }

    cout << ans << endl;
}

复杂度分析

• 时间复杂度： 或

  • 二分查找的范围是 到 ，所以二分的次数是 。
  • 在每次二分检查中，我们需要遍历所有的行（或列，取较小者以优化），这需要 的时间。
  • 总时间复杂度为 。

• 空间复杂度：

注意事项

1. 数据类型： 最大可达 ，超过了 32 位整数（int）的范围，因此在计算 、中间值 以及累加计数 时，必须使用 64 位整数。
2. 边界条件： 或 的情况通过二分逻辑均可自然处理。
3. 优化：在 Check 函数中，遍历行 到 或者遍历列 到 都是可以的。为了进一步优化，可以选择遍历 ，但这在 同阶时并不改变复杂度级别。