[3020] 개똥벌레

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

3020번: 개똥벌레

 

 

만약 N과 H가 조금만 작았더라면, 단순히 앞뒤를 뒤집은 석순과 종유석의 높이의 기준만 잘 설정해주어 선형탐색으로 풀 수 있었을 것이다.

어처피 데이터의 순서가 무의미하니, 석순과 종유석이 정렬되었다고 가정하고 시작해보면,

어떤 하나의 높이 i에 대해서, lower_bound(i) 이전의 장애물은 파괴할 필요가 없는 장애물이고,

lower_bound(i) 이후의 장애물은 모두 파괴해야 하는 장애물이 된다.실제로 종유석과 석순이 뒤바뀌어 있기에 off-by-one 실수의 가능성이 크다.

 

반대로 높이 i로 지나갈때, 석순과 종유석이 모두 걸리면서 높이의 합이 최소인 경우를 생각해보면,높이 i를 제외한 [1, i)와 (i, H]는 전부 석순 혹은 종유석이 하나 존재하고,높이 i에만 석순과 종유석이 모두 존재하는 형태가 되게된다.그렇기에, 종유석 vector와 석순 vector를 대상으로, lower_bound()에 들어가는 target의 합은 H+1이 되어야 한다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, S, ans = 1e9, ansCnt;

int c(int idx) { return S - idx; }

int main(void) {

    if (!local) {

        ios_base::sync_with_stdio(0);

        cin.tie(0);

    }

    cin >> n >> m;

    S = n / 2;

    int i;

    vector<int> u(S), d(S);

    for (i = 0; i < S; i++) cin >> d[i] >> u[i];

    sort(u.begin(), u.end());

    sort(d.begin(), d.end());

    for (i = 1; i <= m; i++) {

        int cur = c(lower_bound(u.begin(), u.end(), i) - u.begin()) +

                  c(lower_bound(d.begin(), d.end(), m - i + 1) - d.begin());

        if (cur < ans) {

            ans = cur;

            ansCnt = 1;

        } else if (cur == ans)

            ansCnt++;

    }

    cout << ans << ' ' << ansCnt;

    return 0;

}

---