Milk Buckets
플래티넘 II의견: 0
Bessie has challenged Farmer John to a game involving milk buckets! There are
\(N\) \((2 \leq N \leq 2 \cdot 10^5)\) milk buckets lined up in a row. The \(i\)-th
bucket from the left initially contains \(a_i\) \((0 \leq a_i \leq 10^9)\) gallons
of milk.
The game consists of two phases:
Phase 1: Farmer John may swap any two adjacent buckets. He may perform as many
swaps as he likes, but each swap costs 1 coin.
Phase 2: After swapping, Farmer John performs the following operation until only
one bucket is left: Choose two adjacent buckets with milk amounts \(a_i\) and
\(a_{i+1}\), and replace both buckets with one bucket containing
\(\frac{a_i+a_{i+1}}2\) gallons of milk in their place.
Your goal is to determine the minimum number of coins Farmer John must spend in
the swapping phase to maximize the amount of milk in the final bucket after all
merges are complete.
Problem credits: Charlie Yang
SCORING
- Inputs 3-4: \(a_i\le 1\) and \(N\le 2000\) (sum of \(N\le 5000\))
- Inputs 5-6: \(a_i\le 1\)
- Inputs 7-9: \(N\le 2000\) (sum of \(N\le 5000\))
- Inputs 10-14: No additional constraints.
Problem credits: Charlie Yang
The first line contains one integer \(T\) \((1 \leq T \leq 100)\): the number of
independent test cases.
Then, for each test case, the first line contains an integer \(N\): the number of
milk buckets. The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\),
separated by spaces: the number of gallons of milk in each bucket.
It is guaranteed that the sum of \(N\) over all test cases does not exceed
\(5 \cdot 10^5.\)
For each test case, output the minimum number of coins Farmer John must spend to
maximize the amount of milk in the final bucket.
2
3
0 0 1
3
0 1 00
1For 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.
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 131
2
0
3For 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
평가 및 의견
Milk Buckets
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Milk Buckets