ARC037 C 億マス計算
問題
方針
$f(x)$ を表全体に含まれる $x$ 以下の数の個数と定義すると、 $f(x) \geq K$ となる最小の $x$ が答えとなります。 $f(x)$ は単調増加なのでそのような $x$ は二分探索で求めることができます。
$f(x)$ を計算するのも二分探索で可能で、 全ての行をはじめにソートしておくと、 $i$ 行目に $b_i x$ 以下の数がいくつ含まれるかを求められます。 これを各行について求めて足し合わせます。
全体の時間計算量は $O(N \log ( N ) \log ( \max a_i b_i ) )$ です。
実装
// x以下の数の個数
int f(int N, int K, vi & a, vi & b, int x){
int cnt = 0;
rep(i,N){
int l = -1;
int r = N;
while(l+1 < r){
int m = (l+r)/2;
if(a[i] * b[m] <= x){
l = m;
} else {
r = m;
}
}
cnt += r;
}
return cnt;
}
int solve(int N, int K, vi & a, vi & b){
sort(all(a));
sort(all(b));
int l = 0;
int r = a[N-1]*b[N-1];
while(l + 1 < r){
int m = (l+r)/2;
int c = f(N,K,a,b,m);
dump(m,c);
if(c >= K){
r = m;
} else{
l = m;
}
}
return r;
}
signed main(){
int N,K;
vi a(N), b(N);
rep(i,N) cin >> a[i];
rep(i,N) cin >> b[i];
cout << solve(N,K,a,b) << endl;
}