Xô Sữa

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie thách Farmer John với trò chơi gồm $N$ xô sữa xếp hàng, xô thứ $i$ chứa $a_{i}$ gallon sữa.

Pha 1: Hoán đổi hai xô liền kề (mỗi lần hoán đổi tốn 1 đồng), thực hiện bao nhiêu lần tùy ý.

Pha 2: Lặp lại: chọn hai xô liền kề với lượng sữa $a_{i}$ và $a_{i + 1}$ , thay cả hai bằng một xô chứa $\frac{a_{i} + a_{i + 1}}{2}$ gallon, cho đến khi còn 1 xô.

Mục tiêu: tối thiểu hóa số đồng trong Pha 1 để tối đa hóa lượng sữa cuối cùng.

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số test case
Mỗi test case:
- Dòng 1: Số nguyên $N$
- Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$

Dữ liệu ra

Với mỗi test case, in ra số đồng tối thiểu cần chi.

Ràng buộc

$1 \leq T \leq 100$
$2 \leq N \leq 2 \times 10^{5}$
$0 \leq a_{i} \leq 10^{9}$
Tổng $N$ qua tất cả test case $\leq 5 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
2 3 0 0 1 3 0 1 0	0 1	Test 1: [0,0,1] tối ưu rồi. Test 2: đổi thành [0,0,1] hoặc [1,0,0] tốn 1 đồng.

Bình luận

Không có bình luận tại thời điểm này.