임프 2

1. 전략을 순서로 표현하기

당신이 상자를 샀는데 임프가 주문을 쓰지 않으면 게임은 즉시 끝난다. 따라서 게임이 계속되는 경우는 방금 산 아이템이 사라진 경우뿐이다. 즉, 당신의 전략은 서로 다른 상자들의 순서

$$p_1,p_2,\ldots$$

로 나타낼 수 있다.

양의 정수 $x$ 이상의 이익을 반드시 얻고 싶다고 하자. 임프는 처음 $k$개의 아이템을 모두 없앨 수 있으므로, 아이템을 얻어 이익 $x$ 이상을 보장하려면 적어도 $k+1$개의 상자를 살 계획이 필요하다. 반대로 $k+1$개의 상자를 계획하면 임프는 그중 하나를 반드시 남겨야 한다.

$p_i$번 상자에서 처음으로 아이템을 얻는 경우 지금까지 지불한 금액은

$$\sum_{j=1}^{i} c_{p_j}$$

이고 이익은

$$v_{p_i}-\sum_{j=1}^{i} c_{p_j}$$

이다. 따라서 이익 $x$ 이상을 보장할 수 있는 필요충분조건은 서로 다른 $k+1$개의 상자를 어떤 순서로 배치하여 모든 $1 \le i \le k+1$에 대해

$$\sum_{j=1}^{i} c_{p_j} \le v_{p_i}-x$$

를 만족시키는 것이다.

이익 $0$은 처음부터 빈손으로 떠나면 항상 얻을 수 있으므로, 최종 답은 음수가 아니다.

2. 스케줄링 문제로 바꾸기

목표 이익 $x$를 고정한다. 각 상자를 다음 작업으로 생각하자.

• 처리 시간: $c_i$
• 마감 시간: $v_i-x$

앞의 부등식은 선택한 작업들을 어떤 순서로 실행했을 때 모든 작업이 자신의 마감 시간 이내에 끝난다는 뜻과 같다. 따라서 목표 이익 $x$가 가능한지는 마감 시간을 지키며 완료할 수 있는 작업이 $k+1$개 이상인지로 판정할 수 있다.

3. 완료 가능한 작업 수의 최댓값

작업을 마감 시간 오름차순으로 본다. 현재까지 선택한 작업들의 처리 시간 합을 $S$라 하고, 선택한 처리 시간들을 최대 힙에 넣는다.

새 작업을 선택한 뒤 $S$가 현재 마감 시간을 초과하면, 선택한 작업 중 처리 시간이 가장 긴 작업 하나를 제거한다. 같은 개수의 작업을 남겨야 할 때 가장 긴 작업을 제거하는 것이 처리 시간 합을 가장 작게 만들기 때문이다.

각 단계가 끝난 뒤 힙에는 지금까지 본 작업들 중 마감 시간을 지키며 완료할 수 있는 최대 개수의 작업이 들어 있다. 또한 그 최대 개수를 만드는 선택 중 처리 시간 합이 최소이다. 이 불변식은 새 작업을 추가한 뒤 마감 시간을 넘지 않는 경우에는 그대로 유지되고, 넘는 경우에는 가장 긴 작업을 제거함으로써 유지된다.

모든 작업을 처리한 뒤 힙의 크기가 $k+1$ 이상이면 목표 이익 $x$가 가능하다.

마감 시간은 $v_i-x$이므로 $x$가 달라져도 작업의 정렬 순서는 $v_i$의 오름차순으로 동일하다. 각 테스트 케이스에서 한 번만 정렬하면 된다.

4. 파라메트릭 서치

어떤 이익 $x$를 보장할 수 있다면 그보다 작은 이익도 보장할 수 있다. 따라서 가능 여부는 단조적이다.

비용은 음수가 아니므로 답은 어떤 아이템의 가치보다 클 수 없고, 모든 $v_i$가 $1\ 000\ 000$ 이하이므로 답의 범위는 $0$ 이상 $1\ 000\ 000$ 이하이다. 이 범위에서 이분 탐색한다.

각 가능 여부 판정은 최대 힙을 사용하여 $O(n\log n)$이고, 이분 탐색은 $O(\log 1\ 000\ 001)$번 수행된다. 전체 시간 복잡도는

$$O(n\log n\log 1\ 000\ 001)$$

이고, 공간 복잡도는 $O(n)$이다. 여러 테스트 케이스에서는 $n$의 합에 대해 같은 복잡도 분석이 적용된다.

Solution written by GPT5.6