c++ - 使用二进制搜索查找 n*m 乘法表中的第 k 个最大数

Question

所以，我正在尝试解决问题:http://codeforces.com/contest/448/problem/D

Bizon the Champion 不仅迷人，而且非常聪明。

当我们中的一些人在学习乘法表时，冠军 Bizon 以他自己的方式玩得很开心。 Bizon the Champion画了一张n⟩×⟩m乘法表，其中第i行第j列相交处的元素等于i·j(表的行和列从1开始编号)。然后问他:表中第k大的数是什么数？ Bizon the Champion 总是正确而迅速地回答。你能重复他的成功吗？

考虑给定的乘法表。如果你从表中按非递减顺序写出所有n·m个数，那么你写出的第k个数称为第k大数。

输入 单行包含整数n，m和k(1 ≤⟩n，⟩m⟩≤⟩5·105；1 ≤⟩k⟩≤⟩n·m)。

输出 打印n⟩×⟩m乘法表中第k大的数。

我所做的是，我应用了从 1 到 n*m 的二进制搜索，寻找正好小于它的 k 个元素的数字。为此，我编写了以下代码:

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
ll n,m;
int f (int val);
int min (int a, int b);
int main (void)
{
    int k;
    cin>>n>>m>>k;
    int ind = k;
    ll low = 1LL;
    ll high = n*m;
    int ans;
    while (low <= high)
    {
        ll mid = low + (high-low)/2;
        if (f(mid) == k)
            ans = mid;
        else if (f(mid) < k)
            low = mid+1;
        else
            high = mid-1;
    }
    cout<<ans<<"\n";
    return 0;

}

int f (int val)
{
    int ret = 0;
    for ( int i = 1; i <= n; i++ )
    {
        ret = ret + min(val/i,m);
    }
    return ret;
}

int min (int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

但是，我不知道为什么，但这对测试用例给出了错误的答案:

input
2 2 2
output
2

我的输出结果是0

我正在学习二进制搜索，但我不知道这个实现哪里出错了。任何帮助将不胜感激。

Answer 1

尽管您的二分查找不是最快的方法，但您仍然想知道为什么它不正确。

首先要非常清楚你想要什么以及你的 f 返回的是什么:

looking for the number which has exactly k elements less than it.

不!您正在寻找具有小于或等于的 k 个元素的最小数字。您的函数 f(X) 返回小于或等于 X 的元素数。

因此当 f(X) 返回的值太小时，您知道 X 必须至少大 1，因此 low=mid+1 是正确的。但是当 f(X) 返回的值太大时，X 可能是完美的(可能是表中多次出现的元素)。相反，当 f(X) 返回完全正确的数字时，X 可能仍然太大(X 可能是在表中出现零次的值)。

所以当 f(X) 不太小时，您能做的最好是 high=mid 而不是 high=mid-1

while (low < high)
{
    ll mid = low + (high-low)/2;
    if (f(mid) < k)
        low = mid+1;
    else
        high = mid;
}

注意 low 永远不会 > high，所以当它们相等时停止，并且我们不会尝试沿途捕获 ans。而不是在最后 low==high==Answer

比赛规定 1 秒的时间限制。在我的计算机上，您的代码经过该更正后可以在一秒钟内解决最大尺寸问题。但我不确定评审计算机有那么快。

编辑:int 对于问题的最大尺寸来说太小了，所以你不能从 f:
返回 int n、m、i各占32位，但f()的输入输出和k、ret、low、high都需要保持2.5e11以内的整数