https://www.acmicpc.net/problem/3020
3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
전형적인 이분탐색문제이다.
주의해야 할 점은 upperbound는 구하고자 하는 값보다 큰 값이 처음으로 나오는 인덱스를 출력하므로 반복문을 돌 때 H를 포함시켜야 한다는 것이다.
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#define endl '\n'
#define ll long long
using namespace std;
int N,H;
vector<int> top;
vector<int> bottom;
void input() {
cin>>N>>H;
int t,b;
for(int i=0;i<N/2;i++){
cin>>b>>t;
bottom.push_back(b);
top.push_back(t);
}
}
void init() {
}
void solution() {
sort(bottom.begin(),bottom.end());
sort(top.begin(),top.end());
int result=INT_MAX,cnt=1;
for(int i=1;i<=H;i++){
int temp=bottom.size()-(lower_bound(bottom.begin(), bottom.end(), i) - bottom.begin());
temp+=top.size()-(upper_bound(top.begin(),top.end(),H-i)-top.begin());
if (result == temp)
cnt++;
else if (result > temp)
{
result = temp;
cnt = 1;
}
}
cout<<result<<" "<<cnt;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
input();
solution();
return 0;
}