用二分查找求n*m乘法表中的第k个最大数

Question

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

冠军比松不仅很有魅力，他也很聪明。

当我们中的一些人在学习乘法表的时候，冠军Bizon以他自己的方式玩得很开心。比松冠军绘制了一个n × m乘法表，其中第i行和第j列交集上的元素等于i·j (表中的行和列从1开始编号)。然后他被问到:表中的第k个最大数字是什么？Bizon冠军总是回答正确和及时。你能重复他的成功吗？

考虑给定的乘法表。如果你以非递减顺序写出表中所有的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返回什么：

查找恰好少于k个元素的数字。

不是的！您正在寻找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的整数

Answer 2

import java.util.*;
public class op {
    static int n,m;
    static long k;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        n=s.nextInt();
        m=s.nextInt();
        k=s.nextLong();
        long start=1;
        long end=n*m;
        long ans=0;
        while(end>=start){
            long mid=start+end;
            mid/=2;
            long fmid=f(mid);
            long gmid=g(mid);
            if(fmid>=k && fmid-gmid<k){
                ans=mid;
                break;
            }
            else if(f(mid)>k){
                end=mid-1;
            }
            else{
                start=mid+1;
            }
        }
        System.out.println(ans);

    }
    static long f (long val)
    {
        long ret = 0;
        for ( int i = 1; i <= n; i++ )
        {
            ret = ret + Math.min(val/i,m);
        }
        return ret;
    }
    static long g (long val)
    {
        long ret = 0;
        for ( int i = 1; i <= n; i++ )
        {
            if(val%i==0 && val/i<=m){
                ret++;
            }
        }
        return ret;
    }
    public static class Pair{
        int x,y;
        Pair(int a,int b){
            x=a;y=b;
        }
    }
}