页面无法加载？点击这里可能会修复。
Placeholder

#8859
子任务

우유 양동이 1s 1024MB

问题

베시는 농부 존에게 우유 양동이를 이용한 게임을 도전했다!
일렬로 놓인 우유 양동이가 N개(2≤N≤2⋅10^5) 있으며, 왼쪽에서 i번째 양동이에는 처음에 a_i (0≤a_i≤10^9) 갤런의 우유가 들어 있다.

이 게임은 두 단계로 이루어져 있다.

1단계:
농부 존은 서로 인접한 두 양동이를 아무 쌍이나 서로 바꿀 수 있다.
원하는 만큼 교환할 수 있지만, 각 교환에는 동전 1개가 든다.

2단계:
교환이 끝난 후, 농부 존은 양동이가 하나만 남을 때까지 다음 연산을 수행한다:
우유의 양이 a_i와 a_{i+1}인 서로 인접한 두 양동이를 선택하여, 그 자리에 우유가 \frac{a_i+a_{i+1}}{2} 갤런 들어 있는 하나의 양동이로 두 양동이를 대체한다.

당신의 목표는 모든 병합이 완료된 후 최종 양동이에 들어 있는 우유의 양을 최대화하기 위해, 농부 존이 교환 단계에서 지불해야 하는 동전의 최소 개수를 구하는 것이다.


输入

첫 번째 줄에는 독립적인 테스트 케이스의 개수를 나타내는 정수 T (1≤T≤100)가 주어집니다.

그 다음, 각 테스트 케이스에 대해 첫 번째 줄에는 우유 양동이의 개수를 나타내는 정수 N이 주어집니다. 두 번째 줄에는 각 양동이에 들어 있는 우유의 양(갤런)을 나타내는 N개의 정수 a_1,a_2,…,a_N이 공백으로 구분되어 주어집니다.

모든 테스트 케이스에 대한 N의 합은 5⋅10^5을 초과하지 않음이 보장됩니다.


输出

각 테스트 케이스에 대해, 마지막 양동이에 담긴 우유의 양을 최대화하기 위해 존 농부가 소비해야 하는 최소 동전 수를 출력하세요.


子任务

编号 分数 条件
#110分

a_i≤1 이고 N≤2000 (N의\ 합≤5000)

#220分

a_i≤1

#330分

N≤2000 (N의\ 합≤5000)

#440分

추가 제약 조건 없음


示例 #1

2
3
0 0 1
3
0 1 0
0
1

첫 번째 테스트의 경우, 첫 번째 단계에서 우유 양동이를 교체할 필요가 없습니다. 두 번째 단계에서 존 농부는 처음 두 양동이를 합친 다음 남은 두 양동이를 합쳐 최종 양 0.5를 얻을 수 있습니다. 이 최종 양이 최대임을 보일 수 있습니다.

두 번째 테스트의 경우, 두 번째 단계에서 최종 양 0.5를 얻기 위해 첫 번째 단계에서 처음 두 우유 양동이를 한 번 교체해야 합니다. 첫 번째 단계에서 교체 없이는 최종 양 0.5를 얻을 수 없음을 보일 수 있습니다.


示例 #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
1
2
0
3

来源

USACO 2026 First Contest, Gold
需要登录才能编写代码。