Problem
Concept & Idea
우선 종유석과 석순을 구분하여 배열에 넣었다.
그리고 lower_bound와 upper_bound를 이용해서 장애물의 수를 count하고 배열에 높이의 수를 기록한다.
마지막에 최솟값을 출력하기 위해서, 원래 포문을 1부터 n까지 돌려야했는데 생각해보니 장애물이 0일수도 있기 때문에 이를 고침으로 맞을 수 있었다.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,h;
int map[200001];
vector<int> up, down;
int obstacle[200001];
int main(){
cin>>n>>h;
for(int i=0; i<n; i++)
cin>>map[i];
for(int i=0; i<n; i++) {
if(i%2==0)
down.push_back(map[i]);
else
up.push_back(map[i]);
}
sort(up.begin(), up.end()); sort(down.begin(), down.end());
for(int i=1; i<=h; i++) {
int downIndex=lower_bound(down.begin(), down.end(), i)-down.begin();
int temp = down.size()-downIndex;
int upIndex = upper_bound(up.begin(), up.end(),h-i)-up.begin();
temp+=up.size()-upIndex;
obstacle[temp]++;
}
for(int i=0; i<=n; i++) {
if(obstacle[i]!=0) {
cout<<i<<" "<<obstacle[i]<<endl;
break;
}
}
}
다른 테스트 케이스
input 14 5 1 3 4 2 2 4 3 4 3 3 3 2 3 3 output 7 2
Fealing
파라메트릭 서치인줄 알았는데,, 아니었다.
장애물의 최솟값을 Mid로 두고 서치를 하려고 했는데, 그 문제가 아니었다..
왜냐면 파라메트릭 서치처럼해서 탐색으로 장애물 갯수를 세려면, 거의 삼중 포문이 되어 시간초과가 나버려서 바로 다른 방법을 찾아 풀수있었다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.