Cân bằng dương

Points: 3.4 (partial)

Time limit: 1.0s

Memory limit: 98M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Với mỗi dãy số gồm toàn các số nguyên dương, bạn có thể thực hiện một trong hai thao tác sau bao nhiêu lần tùy ý:

Cân bằng tăng: Chọn một chỉ số $i$ bất kì, tăng tất cả các phần từ chỉ số khác $i$ lên $1$ .
Cân bằng giảm: Chọn một chỉ số $i$ bất kì, giảm tất cả các phần tử chỉ số khác $i$ đi $1$ .

Chú ý rằng hai thao tác trên chỉ áp dụng cho các dãy số chứa toàn số nguyên dương. Đồng thời, bạn không được cân bằng trên tất cả các chỉ số trong dãy.

Nhập và một dãy số, bạn hãy xác định số thao tác ít nhất để các phần tử trong dãy số đều bằng nhau.

Đầu vào

Dòng đầu chứa số tự nhiên $n$ $(1 \leq n \leq 2 * 10^{5})$ , số phần tử của dãy số.

Dòng tiếp theo chứa $n$ số nguyên dương không quá $10^{6}$ , các phần tử của dãy số.

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán.

Nếu như không có cách nào để cân bằng dãy số sử dụng hai thao tác trên, bạn hãy xuất ra $- 1$ .

Ví dụ

Đầu vào:

Copy

4
1 2 3 4

Đầu ra:

Copy

Giải thích: Giả sử dãy số trên bắt đầu từ chỉ số $1$ , các bước cân bằng dãy số trên như sau:

Cân bằng giảm ở chỉ số $1$ : $1, 1, 2, 3$ .
Cân bằng tăng ở chỉ số $3$ : $2, 2, 2, 4$
Cân bằng tăng hai lần ở chỉ số $4$ : $4, 4, 4, 4$ .

QDUY

Comments

0

MinhDuc_CNTT1_K64 commented on Oct. 15, 2023, 5:40 p.m.

bài này hướng làm như nào vậy ạ :<

4

creator commented on Oct. 16, 2023, 5:38 p.m.

Bạn có thể thay cân bằng tăng tại $i$ bằng thao tác trừ $1$ vào phần tử chỉ số $i$ , cân bằng giảm tại $i$ bằng thao tác cộng $1$ vào phần tử chỉ số $i$ $\to$ đưa về vấn đề Que củi, với điều kiện là chỉ được cân bằng khi các phần tử trong dãy số đều dương. Bài Lucky phát quà cũng giải tương tự.

2

creator commented on Oct. 15, 2023, 3:30 a.m.

Lucky phát quà