BOJ 19845 C++

문제접근

편의상 제거할 수 있는수를 kill이라고 하겠다.
입력받은 넴모의 수를 배열로 받아준다.
xKill = arr[y - 1] - (x - 1)과 같다.
yKill을 구하는게 이문제의 핵심인데 이분탐색으로 배열에서 x좌표의 값보다 작거나 같은수의 가장 큰 인덱스를 찾으면 된다. 예제처럼 3,3,2가 주워졌을때 yKill을 구하는 방법은 x와 작거나 같은수의 가장 큰 인덱스를 배열에서 찾으면 0,1,2즉 3이 인덱스이다. 이 인덱스는 ykill의 최대값이므로 여기서 y좌표로 받은값을 빼주면 ykill이 된다.
정답은 xkill과 ykill이 겹치므로 -1을 해준다. 그리고 0보다 작으면 안되므로 작을시에 0을 출력한다.

형편없는 그림이지만 참고가 될지도(?)

즉 x보다 작거나 같은값의 최대 인덱스가 y그 x좌표에서 ykill의 최대값이 된다.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;
int f[250001];
int n, q;

int ebun(int val)
{
	int lo = 0;
	int hi = n - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (val > f[mid])
			hi = mid - 1;
		else
			lo = mid + 1;

	}
	return lo;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> q;

	for (int i = 0; i < n; i++)
		cin >> f[i];
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		int xkill = f[y - 1] - (x - 1);
		int yKill = ebun(x) - (y - 1);
		cout << max(0, xkill + yKill - 1) << "\n";
	}
	return 0;
}