세 명이 모이면 한 명은 세종대생이다 2

최소 힙은 priority_queue<long long, vector<long long>, greater<long long>>으로 만든다. 각 $b_i$를 두 번 넣고 top()을 읽어 제거한 뒤 $b_i$와의 차를 비용에 더한다. 위치 변환, 기본 비용과 누적 비용은 long long으로 계산한다. $N>3K+2$인 경우는 힙을 만들기 전에 불가능으로 처리한다.

S 위치는 1-based로 모으고 N>3*K+2이면 -1을 출력한다. a_i와 clip값은 int에 들어가지만 전체 비용은 long long이다. 최소 힙에 clip값을 두 번 넣고 한 번 빼는 갱신을 그대로 구현한다.

heapq 최소 힙을 사용한다. 각 b를 두 번 heappush하고 한 번 heappop하여 b-y를 답에 더한다. 위치는 1-based이며 clip으로 생긴 기본 비용도 더한다. Python int로 큰 교환 합을 저장한다.

불가능 조건을 통과한 뒤, positions에는 $1$부터 센 S의 위치를 둔다. 기본 비용을 먼저 더한 다음 힙으로 순서 보정 비용을 더한다.

import heapq

bound = n - 3 * len(positions) - 2
heap = []
answer = 0
for i, p in enumerate(positions, 1):
    a = p - 3 * i
    b = min(0, max(bound, a))
    answer += abs(a - b)
    heapq.heappush(heap, b)
    heapq.heappush(heap, b)
    answer += b - heapq.heappop(heap)

PriorityQueue<Integer>를 최소 힙으로 사용하고 비용 합은 long으로 둔다. b를 두 번 offer한 뒤 poll하고 차이를 더한다. 불가능 조건을 먼저 검사하고 Math.abs(a-b) 기본 비용을 빠뜨리지 않는다.

불가능 조건을 통과한 뒤, positions에는 $1$부터 센 S의 위치를 둔다. 두 번 삽입·한 번 삭제와 기본 이동 비용을 모두 반영한다.

PriorityQueue<Integer> heap = new PriorityQueue<>();
int bound = n - 3 * positions.size() - 2;
long answer = 0;
for (int i = 0; i < positions.size(); i++) {
    int a = positions.get(i) - 3 * (i + 1);
    int b = Math.min(0, Math.max(bound, a));
    answer += Math.abs(a - b);
    heap.offer(b);
    heap.offer(b);
    answer += b - heap.poll();
}

BinaryHeap<Reverse<i64>>로 최소 힙을 만든다. b를 두 번 넣고 한 번 꺼낸 뒤 b-y를 i64 답에 더한다. clip과 위치 계산도 부호 있는 자료형으로 하여 음수 B를 표현한다.

불가능 조건을 통과한 뒤, positions에는 $1$부터 센 S의 위치를 둔다. Reverse를 씌워 가장 작은 값을 꺼낸다.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

let bound = n as i64 - 3 * positions.len() as i64 - 2;
let mut heap = BinaryHeap::new();
let mut answer = 0i64;
for (i, &p) in positions.iter().enumerate() {
    let a = p as i64 - 3 * (i as i64 + 1);
    let b = a.clamp(bound, 0);
    answer += (a - b).abs();
    heap.push(Reverse(b));
    heap.push(Reverse(b));
    answer += b - heap.pop().unwrap().0;
}

문자열에서 S의 위치를 $1$부터 세어 모은다. 불가능 조건 n > 3 * k + 2를 먼저 처리하고, 각 위치의 a = position - 3 * i를 $[B,0]$에 잘라 기본 비용을 더한다. 이때 $i$도 $1$부터 시작한다.

JS에는 표준 최소 힙이 없으므로 숫자 배열과 push·pop 함수로 이진 힙을 구현한다. 부모 값이 자식 값 이하가 되도록 삽입 시 위로 올리고, 최솟값을 제거한 뒤에는 마지막 값을 루트에 놓고 더 작은 자식과 교환하며 내려간다. 각 값 $b$를 두 번 넣고 최솟값을 한 번 꺼내 b - min을 답에 더한다. 같은 값의 꺾임점도 두 개 남겨야 하므로 집합으로 대체하지 않는다.

교환 비용은 최대 $NK\le4\cdot10^{10}$ 수준이어서 Number로 정확하지만 $32$비트를 넘는다. 답을 정수 배열에 넣지 않는다. 최종 배치 자체나 모든 교환을 복원할 필요는 없으며, 시간은 공통 풀이의 $O(N+K\log(K+1))$이다.