분명 정렬 안 되어 있는 거 같은데 이분 탐색 써야할 때(백준 31848)

문제부터 빠르게 살펴보자

 

https://www.acmicpc.net/problem/31848

 

도토리가 빠지는 구멍들이 정렬이 안 되어 있어 이분 탐색에 어려워보인다.

 

하지만 시뮬레이션을 생각해보면, 어차피 큰 구멍 사이에 있는 작은 구멍은 의미가 없다.

 

이런 경우에는 기존에 더 큰 값으로 덮어씌워도 된다. 그러면 최대값을 갱신해가며 기록하면 된다.

 

즉 오름차순으로 배열이 생겨나게 된다. 여기서 lower_bound 를 깔끔하게 써주면 문제를 해결할 수 있다.

 

코드

#include<iostream>
#include<vector>
using namespace std;
int N, M;
vector<int> minHoles;
int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> N;
	int maxV = 0;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		temp += i;
		maxV = (maxV < temp) ? temp : maxV;
		minHoles.push_back(maxV);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int temp;
		cin >> temp;
		int t = lower_bound(minHoles.begin(), minHoles.end(), temp) - minHoles.begin();
		t++;
		cout << t << " ";
	}

	return 0;
}