candypinkmagicholeflipflop

동전을 $X_i$의 오름차순으로 정렬하자. 정렬된 순서에서 $i$번째 동전의 가중치를 $w_i$라고 하자.

서로 다른 두 동전이 모두 앞면을 보이면 보이는 수의 합은 항상 $S$ 이상이고, 모두 뒷면을 보이면 항상 $S$ 미만이다. 앞면과 뒷면이 이웃할 때는 뒷면 동전의 $X$가 앞면 동전의 $X$보다 클 때에만 조건이 성립한다.

앞에서 $i$개의 동전만 보았을 때 그중 뒤집은 동전의 수를 $f_i$라고 하자. 원의 일부분에 있는 뒤집은 동전의 양옆은 서로 다른, 더 작은 $X$를 가진 뒤집지 않은 동전이다. 따라서 전체 원이 모두 이 부분에 포함되는 예외를 제외하면, 이 부분에서 뒤집지 않은 동전은 뒤집은 동전보다 적어도 하나 더 많다. 즉, 가능한 선택은 다음을 만족한다.

$$f_i \le \left\lfloor \frac{i-1}{2} \right\rfloor \quad (1 \le i < N), \qquad f_N \le \left\lfloor \frac{N}{2} \right\rfloor.$$

이 조건은 충분하기도 하다. 뒤집지 않은 동전을 $X$의 오름차순으로 $u_1,u_2,\ldots,u_m$, 뒤집은 동전을 라 하자. 이면 의 순서로 배치할 수 있다. 이면 를 원형으로 배치할 수 있다. 위의 접두 구간 조건으로부터 이웃한 모든 앞면·뒷면 쌍에서 뒷면 동전의 가 더 크다는 것을 알 수 있다.

따라서 각 접두 구간에 대해 뒤집은 동전 수의 상한만 지키면서 가중치 합을 최대로 만들면 된다. 동전을 정렬된 순서대로 처리하면서 $w_i$를 최소 힙에 넣고, 힙 크기가 현재 상한을 초과하면 가장 작은 가중치를 제거한다. 각 단계에서 유지되는 선택은 해당 접두 구간 제약을 만족하는 최대 가중치 선택이다. 모든 원소를 처리한 후 힙에 남은 값의 합이 정답이다.

정렬과 힙 연산에 $O(N\log N)$ 시간, $O(N)$ 공간이 필요하다.

Solution written by GPT6