[C++] 백준 BOJ 2110 공유기 설치 (실패)

틀림

 

// BOJ 2110 공유기 설치
#include <bits/stdc++.h>
 
using namespace std;
 
struct node {
    int from;
    int to;
 
    // 우선순위큐 comparator
    bool operator<(const node a) const {
        return (to - from) < (a.to - a.from);
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num, ap;
    cin >> num >> ap;
    int input, s = 1000000000, e = 1;
    vector<bool> house(1000000001, false);
    while (num--) {
        cin >> input;
        house[input] = true;
        s = min(s, input);
        e = max(e, input);
    }
 
    priority_queue<node> arr;
    arr.push({s, e});
    int result = e - s;
    ap -= 2; // 맨앞, 맨뒤 공유기
 
    while (ap--) {
        node nn = arr.top();
        arr.pop();
        s = nn.from;
        e = nn.to;
        int mid = (s + e) / 2;
        if (house[mid]) {
            // mid를 기준으로 2분할
            arr.push({s, mid});
            arr.push({mid, e});
            // 분할 구간 중 작은 값 취하기
            result = min(result, min(mid - s, e - mid));
        } else {
            // 중간 값의 근사 값 구하기
            int left = mid, right = mid;
            while (!house[--left]);
            while (!house[++right]);
            // mid가 s~e 사이에 존재해야 함
            if (left > s || right < e) {
                mid = (mid - left) < (right - mid) ? left : right;
                arr.push({s, mid});
                arr.push({mid, e});
                result = min(result, min(mid - s, e - mid));
            } else ap++; // s~e 사이에 mid가 없는 경우
        }
    }
    cout << result;
 
    return 0;
}