使用二進制搜索找到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; 
     } 
    } 
}