[C/C++ 백준 3020번] 개똥벌레 (Gold 5)

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

3020번: 개똥벌레

막상 푸려면 되게 번거로운 문제. 이분 탐색에만 초점을 두다가 모르겠어서 냅뒀는데, 일단 모든 칸의 장애물 개수를 계산해도 시간초과가 나질 않는다.

 

그래서 기본 구조는 모든 칸을 계산 ==> 가장 적은 칸들의 개수랑 장애물이 몇 개인지 세주기이다.

기본적으로 정렬을 이용하고, algorithm에서 제공하는 lower_bound, upper_bound 를 이용했다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int down[500001]={}, up[500001]={}, total[500001]={};
int main(void){
	int N, H, a, b;
	scanf("%d %d", &N, &H);
	for(int i=0; i<N/2; i++){
		scanf("%d %d", &a, &b);
		down[a]++;
		up[b]++;
	}
	for(int i=H; i>1; i--){
		down[i-1] += down[i];
		up[i-1] += up[i]; 
	}
	for(int i=1; i<=H; i++)
		down[i] += up[H-i+1];
	sort(down, down+H+1);
	int lower = lower_bound(down+1, down+H+1, down[1]) - (down+1) + 1;
	int upper = upper_bound(down+1, down+H+1, down[1]) - (down+1) + 1;
	printf("%d %d",down[1], upper - lower);
}