BOJ 27232 - 청소

BOJ 27232 - 청소

set 을 잘 활용하면 풀리는 문제

어떠한 $K$ 길이의 구간은 경로의 사슬을 이루는데, 슬라이딩 윈도우를 하며 제일 왼쪽 것을 경로에서 제거하고 그 옆에 있던 것 두 개를 이어주고(시작이나 끝일 경우 끊어주기만), 추가해주는 것도 유사하게 처리한다.

$O(n \log n)$에 풀린다.

void solve() {
   int n, k;
   cin >> n >> k;
   if (k == 1) {
      cout << 0;
      return;
   }
   vi a(n);
   fv(a);
   int ans = 2e15;
   vector<pi> idx;
   set < pi > s;
   for (int i = 0; i < k; i++) {
      idx.pb({a[i], i});
      s.insert({a[i], i});
   }
   sort(all(idx), greater<>());
   int tmp = 0;
   for (int i = 1; i < k; i++) {
      tmp += abs(idx[i].se - idx[i - 1].se);
   }
   ans = tmp;
   for (int i = k; i < n; i++) {
      // i - k 번째의 인접한 두 개의 거리만큼 정답에서 빼고
      // 그 두개의 거리만큼 정답에 더한다.
      //

      pi removed = {a[i - k], i - k};
      auto it = s.find(removed);
      auto nxt = it;
      auto prev = it;
      nxt++;
      if (it == s.begin()) {
         tmp -= abs(nxt->se - removed.se);
      } else if (nxt == s.end()) {
         prev--;
         tmp -= abs(prev->se - removed.se);
      } else {
         prev--;
         tmp -= abs(prev->se - removed.se);
         tmp -= abs(nxt->se - removed.se);
         tmp += abs(prev->se - nxt->se);
      }
      s.erase(it);

      pi added = {a[i], i};
      it = s.insert(added).fi;
      nxt = it, prev = it;
      nxt++;
      if (it == s.begin()) {
         tmp += abs(nxt->se - added.se);
      } else if (nxt == s.end()) {
         prev--;
         tmp += abs(prev->se - added.se);
      } else {
         prev--;
         tmp -= abs(prev->se - nxt->se);
         tmp += abs(added.se - nxt->se);
         tmp += abs(added.se - prev->se);
      }
      mina(ans, tmp);
      debug(s);
   }
   cout << ans;
}