Cân bằng dương
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 \le n \le 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:
4
1 2 3 4Đầu ra:
4Giả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\).
Comments
bài này hướng làm như nào vậy ạ :<
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ự.
Lucky phát quà