首页 > 代码库 > D. Multiplication Table 二分查找

D. Multiplication Table 二分查找

刚做这道题根本没想到二分,最关键是没想出来如何统计在这个矩阵中比一个数小的有几个怎么算,造成自己想了好久最后看了别人的提示才做出来。哎!好久不做题太弱了

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
//    freopen("in.txt","r",stdin);
    long long n,m,k;
    while(cin>>n>>m>>k){
        long long r=n*m,l=1,ans;
        while(r>l){
            long long mid=(r+l)/2;
            long long t=0;
            for(int i=1;i<=n;i++){//统计在这个矩阵中比一个数小的有几个
                t+=min(m,mid/i);
            }
            if(t>=k) r=mid;
            if(t<k) l=mid+1;

        }
        cout<<r<<endl;
    }
}