Coin donation [yukicoder No.817]

https://yukicoder.me/problems/no/817

前提知識

• 二分探索

解説

https://yukicoder.me/submissions/340743

N回操作して、手元にある硬貨を昇順ソートしたときのK番目はなにかという問題。
二分探索の典型テクとして、
【「ある条件でソートしたときのK番目の数を求めよ」というのは、答えの数で二分探索する】
があるので、これを適用しよう。

以下の関数を判定関数とする。
check(x) := x円以下の硬貨の枚数がK枚以上あるか
これで境界線を探したときのng, okのうち、okが答えになる。
check関数では、各操作について、x以下の枚数を足していき、総和がK以上かを判定する。

int N, K, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
int check(int x) {
	ll cnt = 0;
	rep(i, 0, N) {
		if (A[i] <= x) {
			cnt += min(B[i], x) - A[i] + 1;
		}
	}
	return K <= cnt;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i] >> B[i];

	int ng = 0, ok = inf;
	while (ng + 1 != ok) {
		int md = (ng + ok) / 2;
		if (check(md)) ok = md;
		else ng = md;
	}
	cout << ok << endl;
}