矩阵第k个数

第k个数

题意

给定一个 \(n \times m\) 的方格矩阵,第 \(i\) 行 \(j\) 列的方格内元素为 \(i \times j\) (行和列都从 \(1\) 开始编号)。

问这 $n \times m $ 个数中第 \(k\) 小的数字为多少。

\(1 \le n, m \le 5 \times 10^5, 1 \le k \le n \times m\) 。

分析

对于第 \(k\) 小的数字,整个矩阵中至少有 \(k\) 个数字小于等于它。

二分枚举答案 \(x\) ,对于第 \(i\) 行,一共有 \(min(m, x / i)\) 个数字小于等于它。

Code

#include <iostream>
using namespace std;

typedef long long ll;

ll n, m, k;

bool check (ll x)
{
    ll res = 0;
    for (int i = 1; i <= n; i ++ )
        res += min(m, x / i);
    return res >= k;
}

int main ()
{
    cin >> n >> m >> k;
    ll l = 1, r = n * m;
    while(l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}
上一篇:cf264 C. Choosing Balls(dp)


下一篇:贪心牛奶之部分背包问题