N N N 種類の微生物があり、i i i 番の微生物の x x x 日目の個体数は A i + B i x A_i + B_i x A i + B i x です。B i B_i B i を成長係数とよびます。
x x x 日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。
成長係数の小さい順
x x x 日目の個体数の少ない順
どちらも、値が同じなら番号の小さい順に並べます。K K K 種類以上選べる最も早い日 x ≥ 0 x \ge 0 x ≥ 0 を求める問題です。存在しなければ -1 を出力します。
1 ≤ K ≤ N ≤ 10 5 1 \le K \le N \le 10^5 1 ≤ K ≤ N ≤ 1 0 5 、1 ≤ A i , B i ≤ 10 9 1 \le A_i, B_i \le 10^9 1 ≤ A i , B i ≤ 1 0 9 です。
微生物を ( B i , i ) (B_i, i) ( B i , i ) の昇順に並べておきます。選んだ微生物の並びがこの順で、( A i + B i x , i ) (A_i + B_i x, i) ( A i + B i x , i ) も昇順になっていれば条件を満たします。
つまり、( B i , i ) (B_i, i) ( B i , i ) の順に並べた列で、( A i + B i x , i ) (A_i + B_i x, i) ( A i + B i x , i ) の最長狭義増加部分列 (LIS) の長さが、x x x 日目に選べる最大の種類数です。LIS の長さは O ( N log N ) O(N \log N) O ( N log N ) で求まります。
x x x 日目に選べる組は、x + 1 x + 1 x + 1 日目にも選べます。
( B p , p ) < ( B q , q ) (B_p, p) < (B_q, q) ( B p , p ) < ( B q , q ) の 2 つが x x x 日目に条件を満たしているとします。1 日たつと、個体数の差 ( A q + B q x ) − ( A p + B p x ) (A_q + B_q x) - (A_p + B_p x) ( A q + B q x ) − ( A p + B p x ) は B q − B p ≥ 0 B_q - B_p \ge 0 B q − B p ≥ 0 だけ増えます。B p < B q B_p < B_q B p < B q なら差が増えるので順序は保たれ、B p = B q B_p = B_q B p = B q なら差が変わらないので順序も変わりません。
よって、選べる最大の種類数は x x x について広義単調増加です。K K K 種類以上選べる最小の x x x を二分探索 で求めます。
問題文にあるとおり、答えが存在すれば 10 9 10^9 1 0 9 以下です。x = 10 9 + 1 x = 10^9 + 1 x = 1 0 9 + 1 で K K K 種類選べなければ -1 を出力し、選べれば [ 0 , 10 9 + 1 ] [0, 10^9 + 1] [ 0 , 1 0 9 + 1 ] で二分探索します。
全体で O ( N log N log max ) O(N \log N \log \max) O ( N log N log max ) です。
Python
from operator import itemgetter
from bisect import bisect_left
for _ in range ( int ( input ())):
N, K = map ( int , input () . split ())
ABi = [ tuple ( map ( int , input () . split ())) + (i,) for i in range ( N ) ]
ABi. sort ( key = itemgetter ( 1 ))
dp = [ ( 2 * 10 ** 18 , 10 ** 18 ) ] * (N + 1 )
dp[ bisect_left ( dp , (a + b * x, i) )] = (a + b * x, i)
if dp[i] [ 0 ] >= 2 * 10 ** 18 :
sort は安定なので、B i B_i B i だけをキーにしても、B i B_i B i が等しいものは番号順に並びます。q(x) は ( A i + B i x , i ) (A_i + B_i x, i) ( A i + B i x , i ) の LIS の長さを返します。dp[k] は長さ k + 1 k + 1 k + 1 の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。