BOJ 26393 - Čokolade

BOJ 26393 - Čokolade

$I-F$ 가 최소가 되어야 한다.

이득을 $F-I$ 라고 정의해보자.

$c_i \le k_j$ 인 걸 살 때 얻는 이득은 $-c_i$ 이다.

$c_i > k_j$ 인 걸 살 때 얻는 이득은 내가 $k_j$ 를 지불하고 $F$가 $c_i-k_j$ 를 지불하므로 $c_i-2k_j$ 이다.

정렬된 $c$ 를 $k_j$ 를 pivot으로 두고 두 구간으로 나눴을 때 왼쪽과 오른쪽의 끝부터 택하는게 항상 더 이득이다.

$q$가 작다면 이걸 투포인터로 찾을 수 있겠지만 이 문제에선 성질을 관찰해서 삼분탐색을 이용할 수 있다.

$f(r)$ 을 오른쪽 끝에서부터 $r$ 개를 택할 때, 그럼 왼쪽에선 $m_j-r$ 개만큼 택하고 이득값이라고 하자.

$f(r)$이 uni-modal함을 보일수있을까?

나는 일단 못보이겠다. 찍어서 맞췄다 ㅈㅅ. 하지만 밑에 해설을 보면 왜 uni-modal한지 알 수 있다.

에디토리얼 해설을 보면 삼분탐색 말고 이분탐색으로만 풀 수 있다.

일단 왼쪽 초콜릿을 $m$개 고르고 오른쪽 초콜릿을 몇개를 취할지를 이분탐색으로 구하면 된다.

이분탐색이 끝나는 지점은 오른쪽 초콜릿에서 $x$개를 취했을 때 그걸 취했을 때 더 이득이 되지 않는 시점이다.

그 이전 초콜릿까지만 오른쪽에서 취해주면 된다.

아래는 삼분탐색 코드다.

void solve() {  
   int n, q;  
   cin >> n >> q;  
   vi c(n), p(n + 1);  
   fv(c);  
   sort(all(c));  
   for (int i = 0; i < n; i++) p[i + 1] = p[i] + c[i];  
   auto sum = [&](int l, int r) { return p[r + 1] - p[l]; };  
  
   while (q--) {  
      int k, m;  
      cin >> k >> m;  
      int pivot = ubi(c, k);  
      int L = pivot, R = n - pivot;  
      int l = max<int>(0, m - L), r = min(m, R);  
      auto val = [&](int x) -> int {  
         int left = m - x;  
         int right = x;  
         int ret = -sum(0, left - 1);  
         ret += sum(n - right, n - 1) - 2 * k * right;  
         return ret;  
      };  
      int ans = -2e18;  
      while (l < r - 3) {  
         int p = (l * 2 + r) / 3, q = (l + 2 * r) / 3;  
         int pv = val(p), qv = val(q);  
         if (pv > qv) r = q;  
         else l = p;  
      }  
      for (int i = l; i <= r; i++)maxa(ans, val(i));  
      cout << -ans << endl;  
   }  
}