RiseOJ – 우유 양동이

설명

베시가 농부 존에게 우유 양동이를 이용한 게임을 도전했다! $$N$$ $(2 \leq N \leq 2 \cdot 10^5)$ 개의 우유 양동이가 한 줄로 놓여 있다. 왼쪽에서 $$i$$ 번째 양동이에는 처음에 우유가 $$a_i$$ $(0 \leq a_i \leq 10^9)$ 갤런 들어 있다.

게임은 두 단계로 진행된다.

1단계: 농부 존은 인접한 두 양동이를 서로 바꿀 수 있다. 원하는 만큼 바꿀 수 있지만, 한 번 바꿀 때마다 동전 1개가 든다.

2단계: 바꾸기가 끝난 후, 농부 존은 양동이가 하나만 남을 때까지 다음 연산을 수행한다. 우유 양이 $$a_i$$ 와 $a_{i+1}$ 인 인접한 두 양동이를 골라, 두 양동이를 그 자리에서 우유 $\frac{a_i+a_{i+1}}2$ 갤런이 든 하나의 양동이로 교체한다.

모든 병합이 완료된 후 마지막 양동이에 든 우유의 양을 최대화하기 위해, 농부 존이 바꾸기 단계에서 지출해야 하는 동전의 최소 개수를 구하는 것이 목표이다.

Problem credits: Charlie Yang

제약

SCORING

입력 3-4: $a_i\le 1$ 이고 $N\le 2000$ ( $$N$$ 의 합 $\le 5000$ )
입력 5-6: $a_i\le 1$
입력 7-9: $N\le 2000$ ( $$N$$ 의 합 $\le 5000$ )
입력 10-14: 추가 제약 없음.

Problem credits: Charlie Yang

입력 형식

첫째 줄에 독립적인 테스트 케이스의 수인 정수 $$T$$ $(1 \leq T \leq 100)$ 가 주어진다.

각 테스트 케이스에 대해, 첫째 줄에 우유 양동이의 수인 정수 $$N$$ 이 주어진다. 둘째 줄에 각 양동이에 든 우유의 갤런 수를 나타내는, 공백으로 구분된 $$N$$ 개의 정수 $a_1, a_2, \dots, a_N$ 이 주어진다.

모든 테스트 케이스에 걸친 $$N$$ 의 합이 $5 \cdot 10^5$ 를 넘지 않음이 보장된다.

출력 형식

각 테스트 케이스에 대해, 마지막 양동이에 든 우유의 양을 최대화하기 위해 농부 존이 지출해야 하는 동전의 최소 개수를 출력한다.

예제 1

입력

출력

0
1

설명

For the first test, we do not need to swap any milk buckets in the first phase.
In the second phase, Farmer John can merge the first two buckets and then merge
the only two buckets left to achieve a final amount of 0.5. It can be shown that
this final amount is maximal.

For the second test, we must perform a singular swap of the first two milk
buckets in the first stage to achieve a final amount of 0.5 in the second stage.
It can be shown that we cannot achieve a final amount of 0.5 without swaps in
the first stage.

예제 2

입력

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

출력

설명

For the first test, Farmer John can swap the second and the third buckets in the
first phase. Then, in the second phase, Farmer John can perform the following:

$$[9,9,4,2]$$ -> merge the third and fourth buckets ->
$$[9,9,3]$$ -> merge the second and third buckets ->
$$[9,6]$$ -> merge the first and second buckets ->
$$[7.5]$$

The final amount of milk is 7.5, which is the maximum possible. It can be shown
that even with additional swaps, the final amount cannot exceed 7.5, and that
with fewer swaps, the final amount cannot reach 7.5.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Gold

올림피아드 > USACO > 2025-2026 > First Contest > Gold

태그

JudgeUSACO

우유 양동이

평가 및 의견

풀이 제출