使用二进制搜索找到N * M个乘法表k大数字

Question

所以，我试图解决的问题：http://codeforces.com/contest/448/problem/D

BIZON冠军不只是迷人，他也很聪明。

当我们中的一些人正在学习乘法表时，Bizon冠军以他自己的方式玩得很开心。 Bizon Champion绘制了一个n×m的乘法表，其中第i行第j列的交点上的元素等于i·j（表格的行和列从1开始编号）。然后他问道：表中第几个数字是第几个数字？ 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; 
} 

通知低从未得到>高，所以当它们相等时停止，而我们没有试着赶上ans。相反，在最后低==高==答案

比赛说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; 
     } 
    } 
}