ACWing 4080. 第k个数

 1 #include
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,m,k;
 5 int check(LL x)
 6 {
 7     LL s=0,j=m;
 8     for(LL i=1;i<=n;i++)
 9     {
10         while(j&&i*j>x)j--;
11         s+=j;
12     }
13     return s>=k;
14 }
15 
16 int main()
17 {
18     scanf("%lld%lld%lld",&n,&m,&k);
19     LL l=1,r=n*m;
20     while(l<=r)
21     {
22         LL mid=l+r>>1;
23         if(check(mid))r=mid-1;
24         else l=mid+1;
25     
26     }
27     cout<endl;
28     return 0;
29 }

注意到答案为x时 小于等于x-1小的数至多k-1个个数,小于等于x数至少有k个,比x+1小的数至少k个；答案具有单调性二分答案；