无语。。原来这是个水题。。当时看榜过的人并不多题目就没去看
题意:给你一个n * m的矩阵,矩阵中a[i][j]=i * j
q次询问,每次询问矩阵中第k小的元素是多大。
很容易想到二分答案,因为答案具有单调性。
那么对于每一行计算出有多少个≤二分的答案mid的个数,计算一下总个数和k比较即可。
对于每一行,求小于等于mid的数的个数为
N达到了1e8,显然不允许直接算
可以发现上述式子其实就是整除分块(之前的每日一题的数码的知识点)
所以check答案可行性用整除分块来判断,复杂度sqrt(min(n,mid))
总体复杂度 q * log * sqrt(n)
顺便安利一下每日一题的数码,如果没有做过的话
https://ac.nowcoder.com/acm/problem/13221
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,q; bool check(ll mid,ll x){ ll ans=0,l,r; for(l=1;l<=mid&&l<=n;l=r+1){ r=mid/(mid/l); r=min(r,n); ans+=(r-l+1)*min(mid/l,m); } //cout<<mid<<" "<<ans<<" "<<x<<endl; return ans>=x; } int main(){ cin>>n>>m>>q; while(q--){ ll x;cin>>x; ll l=0,r=1e9,mid; while(l+1<r){ mid=l+r>>1; if(check(mid,x)) r=mid; else l=mid; } cout<<r<<endl; } }