3020번 개똥벌레

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

이분 탐색 필수 정렬 lower_bound 복습 추천 upper_bound boj 백준 개똥

처음에 find를 활용했다가 시간 초과 발생.

그래서 lower_bound, upper_bound를 활용했더니 50% 쯤에서 틀렸음.

알고보니 처음에 58, 59번 째 줄 코드를 cnt != 0일 때만 실행되게 했었다.

#include<bits/stdc++.h>
 
using namespace std;
 
int N;
double H;
vector<double> up, down;
map<int, int> m;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
 
    cin.tie(0);
    scanf("%d %lf", &N, &H);
 
    double input;
    for (int i = 0; i < N; i++) {
        scanf("%lf", &input);
        if (i % 2 == 0) {
            down.push_back(input);
        }
        else {
            up.push_back(input);
        }
    }
 
    sort(down.begin(), down.end()); // H
    sort(up.begin(), up.end()); // H - (높이)
 
    int Min = 2e9;
    int ds = down.size();
    int us = up.size();
 
    for (double i = 0.5; i < H; i++) {
        int down_cnt = ds - (lower_bound(down.begin(), down.end(), i) - down.begin());
        int up_cnt = us - (lower_bound(up.begin(), up.end(), H - i) - up.begin());
 
        /*printf("down : 높이 = %lf, down_cnt = %d\n", i, down_cnt);
        printf("  up : 높이 = %lf, up_cnt = %d\n\n", H - i, up_cnt);*/
 
        if (down[N / 2 - 1] < i) {
            down_cnt = 0;
        }
        else if (down[0] > i) {
            down_cnt = ds;
        }
 
        if (up[N / 2 - 1] < H - i) {
            up_cnt = 0;
        }
        else if (up[0] > H - i) {
            up_cnt = us;
        }
 
        int cnt = down_cnt + up_cnt;
 
        Min = min(Min, cnt);
        ++m[cnt];
    }
 
    printf("%d %d\n", Min, m[Min]);
 
    return 0;
}