Codeforces Round 878 (Div. 3) - D. Wooden Toy Festival (1400)

D. Wooden Toy Festival

이분탐색으로 풀 수 있다.

모든 수를 정렬하고 최대 차이가 $m$ 이 가능한지 검사하려면 첫 번째 조각가를 $a_0+m$ 의 능력치를 갖게 하고, 쭉 가다가 $a_0+2m$ 보다 큰 $a_i$ 가 나오면 다시 $a_i+m$ 으로 두 번째 조각가를 설정하는 식으로 진행한다.

그래서 필요한 조각가의 수가 $3$ 이하인 것 중 최소인 $m$을 구하면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   uniq(a);
   n = sz(a);
   if (n <= 3) {
      cout << 0 << endl;
      return;
   }
   int ans = 2e9;
   debug(a);
   int lo = 0, hi = 1e9, ret = -1;
   while (lo <= hi) {
      int m = lo + (hi - lo) / 2;
      int need = 1;
 
      for (int i = 1, j = a[0] + m; i < n; i++) {
         if (a[i] - j > m) {
            j = a[i] + m;
            need++;
         }
      }
 
      if (need <= 3) ret = m, hi = m - 1;
      else lo = m + 1;
   }
   cout << ret << endl;
}