BOJ 16361 - LED

BOJ 16361 - LED

문제를 잘못 읽었고, 모든 오류의 합을 최소화하는 줄 알았다.

게다가 이 문제의 짜증나는점은 물론 입력엔 $v_i < v_j$ 일 때 $l_i \le l_j$ 라는 말이 없긴 하지만 예제에서도 그런 상황을 하나도 안넣어놨다는 것과, $v=0$ 일 땐 무조건 전구가 꺼져있어야 한다는 점 때문에 최저 정답을 다르게 제한해야 된다는 것이다.

예를 들어, $v_0=0$ 이고 $l_0=k$ 라면 오차는 최소 $k$ 여야 한다.

---

여하튼 문제를 푸는 방법은 오류의 단위가 .5 이기 때문에 일단 실수를 다룰 필요는 없이 $l_i$에 $\times 2$ 를 해주고 시작하면 된다.

이후에 이제 최대 오류값 $m$에 대해 이분탐색을 시행한다.

모든 데이터들은 $v_i$ 에 대한 오름차순으로 정렬되어있다고 하자.

일단 $l = [0, m]$ 으로 포함되는애들은 skip하고 넘어가주는게 최적이다.

남은 일은, 나머지 것들을 두 구간으로 나눌 수 있는지 판단해야한다.

각각 좌우로 시작하는 최대, 최소값 prefix 배열을 4개 만든다.

$[i, m]$의 최대값 - 최소값이 $2m$ 이하이고 $[m+1, N-1]$ 의 최대값 - 최소값이 $2m$ 이하이며

$[i,m]$ 의 최대값 - $m$ 이 $[m+1, N-1]$ 의 최소값 + $m$ 보다 이하인 경우가 존재하는지를 검사할 수 있다.

void solve() {
   int n;
   cin >> n;
   vector<pi> a(n);
   for (auto &[i, o]: a) {
      cin >> i >> o;
      o <<= 1;
   }
   sort(all(a));
   debug(a);
   int l = a[0].fi == 0 ? a[0].se : 0, r = 2e17, ret = -1;

   vi lmax(n), lmin(n), rmax(n), rmin(n);
   rmax[n - 1] = rmin[n - 1] = a[n - 1].se;
   for (int i = n - 2; i >= 0; i--) {
      rmax[i] = max(rmax[i + 1], a[i].se);
      rmin[i] = min(rmin[i + 1], a[i].se);
   }

   while (l <= r) {
      int m = l + (r - l) / 2;
      int i = 0;
      while (i < n && a[i].se <= m) i++;

      int can = 1;

      if (i < n) {
         int s = i;
         lmin[s] = a[s].se;
         lmax[s] = a[s].se;
         for (int i = s + 1; i < n; i++) {
            lmin[i] = min(lmin[i - 1], a[i].se);
            lmax[i] = max(lmax[i - 1], a[i].se);
         }
         can = 0;

         if (rmax[s] - rmin[s] <= 2 * m) can = 1;

         for (int i = s; i < n - 1; i++) {
            if (lmax[i] - lmin[i] <= 2 * m && rmax[i + 1] - rmin[i + 1] <= 2 * m
               && lmax[i] - m <= rmin[i + 1] + m) {
               can = 1;
               break;
            }
         }
      }

      if (can) ret = m, r = m - 1;
      else l = m + 1;
   }
   assert(~ret);
   cout << ret / 2;
   if (ret % 2) cout << ".5";
   else
      cout << ".0";
}

signed main() {
   fastio
   solve();
   return 0;
}