오렌지!

서브태스크 1: 첫 번째 사람이 구매하는 오렌지의 집합을 모두 열거한다. 크기가 $K$인 집합마다 만족도를 직접 계산하여 최댓값을 구한다. 시간 복잡도는 $O(N2^N)$, 공간 복잡도는 $O(N)$이다.

전체 풀이: 모든 오렌지를 두 번째 사람이 구매한다고 생각하면 만족도는 $\sum_{i=1}^N b_i$이다. $i$번째 오렌지를 첫 번째 사람에게 넘길 때 만족도는 $a_i$만큼 변한다.

$c_i=a_i-b_i$로 두면, 정확히 $$개의 를 골라 합을 최대화하면 된다. 내림차순으로 정렬한 뒤 가장 큰 개를 고른다. 선택한 값보다 큰 값을 선택하지 않았다면 두 값을 교환하여 합을 늘릴 수 있으므로, 이 선택은 최적이다. 같은 값들의 선택 순서는 상관없다.

정렬한 값을 $c_1\geq c_2\geq\cdots\geq c_N$이라 하면 정답은 다음과 같다.

$$\sum_{i=1}^N b_i+\sum_{i=1}^K c_i$$

정확히 $K$개를 골라야 하므로 선택하는 차이가 음수여도 건너뛰면 안 된다.

케이스당 시간 복잡도는 $O(N\log N)$, 공간 복잡도는 $O(N)$이다. 정답과 계산 중의 합의 절댓값은 $2\times10^{14}$ 이하이며, 차이의 절댓값은 이하이다. 합은 64비트 정수로 저장한다.

Solution written by GPT