Ngủ Trong Lớp

Đ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 hay ngủ gật trong lớp, và bạn thân Elsie đã ghi lại số lần Bessie ngủ gật trong mỗi tiết học. Nhật ký gồm $N$ tiết học, tiết thứ $i$ Bessie ngủ gật $a_{i}$ lần.

Elsie muốn chỉnh sửa nhật ký sao cho tất cả các tiết đều có số lần ngủ gật bằng nhau. Mỗi thao tác chỉnh sửa cho phép Elsie chọn hai tiết liền kề, gộp chúng lại thành một tiết duy nhất (số lần ngủ gật của tiết mới bằng tổng hai tiết cũ), đồng thời giảm tổng số tiết đi 1.

Hãy tìm số thao tác gộp tối thiểu để tất cả các tiết còn lại có số lần ngủ gật bằng nhau.

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số bộ test
Với mỗi bộ test:
- Dòng 1: Số nguyên $N$ — số tiết học
- Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — số thao tác gộp tối thiểu.

Ràng buộc

$1 \leq T \leq 10$
$1 \leq N \leq 10^{5}$ , tổng $N$ qua các bộ test $\leq 10^{5}$
$0 \leq a_{i} \leq 10^{6}$ , tổng $a_{i}$ qua tất cả các tiết $\leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 6 1 2 3 1 1 1 3 2 2 3 5 0 0 0 0 0	3 2 0	Test 1: Gộp thành 3 tiết [3, 3, 3], cần 3 thao tác. Test 2: Gộp thành 1 tiết [7], cần 2 thao tác. Test 3: Đã bằng nhau.

Bình luận

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