[백준(BOJ) 16361번] LED 풀이

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

16361번: LED

이 문제는 2018 ACM-ICPC Seoul Regional E번 문제다.

 

실험에서 나오는 l 값들은 정수이므로 error의 단위는 0.5 단위라는 것을 알 수 있다.

 

우리는 error에 대해 0.5 단위로 parametric search를 하면 된다. 즉, error가 하나 정해졌을 때, L1과 L2를 적당히 잡을 수 있는지 물어보는 문제로 바꿀 수 있다.

 

실험 데이터를 v 값에 따라 오름차순으로 정렬해 두자.

 

일단, v가 작은 실험 데이터부터 l 값이 [0, error] 안에 들어오는 것들은 모두 첫 번째 구간으로 넣는 것이 이득이다.

 

이제 두 번째 구간과 세 번째 구간의 경계를 왼쪽부터 오른쪽까지 옮기면서, 두 번째 구간에 있는 실험 데이터는 [L1-error, L1+error], 세 번째 구간에 있는 실험 데이터는 [L2-error, L2+error] 안에 들어오는 지 확인한다. 이 때, L1<=L2를 만족하는지도 확인해야 한다.

 

시간복잡도는 O(n log l)이다.

#include <bits/stdc++.h>

using namespace std;

struct Experiment {
    int v, l;

    bool operator<(const Experiment &a) { return v < a.v; }
} data[300000];

int lmax[300000], lmin[300000], rmax[300000], rmin[300000];

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> data[i].v >> data[i].l;
    sort(data, data + n);  // v 순으로 정렬한다.

    // Parametric search
    // low는 (0, l)이 나왔을 때 최소 error는 l이므로 다음과 같이 설정.
    double low = (data[0].v == 0 ? data[0].l : 0.0), high = 1e9, answer;
    while (low <= high) {
        double error = floor(low + high) / 2.0;  // 0.25->0.0, 0.75->0.5로 버림한다.

        int left;  // i가 [0, left) 구간에 있을 때는 F(data[i].v) = 0.
        for (left = 0; left < n; left++) {
            if (error < data[left].l) break;
        }

        // lmax, lmin은 왼쪽부터 최대, 최소.
        lmax[left] = data[left].l, lmin[left] = data[left].l;
        for (int i = left + 1; i < n; i++) {
            lmax[i] = max(lmax[i - 1], data[i].l);
            lmin[i] = min(lmin[i - 1], data[i].l);
        }
        // rmax, rmin은 오른쪽부터 최대, 최소.
        rmax[n - 1] = data[n - 1].l, rmin[n - 1] = data[n - 1].l;
        for (int i = n - 2; i >= left; i--) {
            rmax[i] = max(rmax[i + 1], data[i].l);
            rmin[i] = min(rmin[i + 1], data[i].l);
        }

        bool possible = false;
        if (left >= n - 1) possible = true;  // 하나만 빼고 첫 번째 구간에 들어갈 경우 성공.
        else {
            for (int i = left + 1; i < n; i++) {
                double L1 = lmax[i - 1] - error, L2 = rmin[i] + error;
                if (lmin[i - 1] >= L1 - error && rmax[i] <= L2 + error && L1 <= L2) {
                    possible = true;  // 두 번째 구간, 세 번째 구간의 밝기를 적절하게 줄 수 있을 경우.
                    break;
                }
            }
        }

        if (possible) {
            answer = error;
            if (low >= high) break;
            high = error - 0.5;
        } else {
            if (low >= high) break;
            low = error + 0.5;
        }
    }

    cout << fixed;  // 소숫점 첫째 자리까지 출력한다.
    cout.precision(1);
    cout << answer;
    return 0;
}