EQARR - Biến đổi dãy số
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.05s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy số gồm ~N~ nguyên dương. Hãy tìm số lần biến đổi tối thiểu để biến đổi các phần tử trong dãy số đó đều bằng nhau theo quy tắc mỗi lần biến đổi thì chỉ có thể tăng ~N - 1~ phần tử lên ~1~ đơn vị.
Input
Dòng đầu tiên ghi số nguyên dương ~N (1 \le N \le 10^5)~,
Dòng tiếp theo ghi ~N~ số nguyên dương ~A_1, A_2, A_3, ..., A_N (1 \le A_i \le 10^9)~
Output
Gồm ~1~ dòng duy nhất là đáp án của bài toán trên.
Sample
Input #1
3
1 2 3
Output #1
3
Hint
Ở #1, ta biến đổi như sau:
- Bước ~1~: ~2, 3, 3~
- Bước ~2~: ~3, 4, 3~
- Bước ~4~: ~4, 4, 4~
Bình luận
tuc la bai nay de toi uu chung ta khong nen tang theo cach cua vi du (1 2 3) -> (2 3 3) -> (3 4 3) -> (4 4 4)
chung ta nen (1, 2, 3) -> (2, 3, 3) -> (3, 3, 4) -> (4, 4, 4)
chung ta sap xep lai sau do
chung ta di tu trai qua phai va tang den khi nao 2 gia tri lien ke nhau bang nhau la duoc
tuc la giu nguyen phan tu lon hon va tang tat ca cac phan tu con lai
1 2 4 5 -> 2 2 5 6 -> 3 3 5 7 -> 4 4 5 8 -> 5 5 5 9 -> 6 6 6 9 -> 7 7 7 9-> 8 8 8 9 -> 9 9 9 9 -> xong
vaiz, biết sai đâu rồi (nhưng không hiểu)
min của mảng để int thì AC, long long là WA :0
sợ test sai vì ~minarr * n~ hoàn toàn ra long long nhưng nộp int nhân int mới đúng :))
ai AC đọc stk ._.
thuật tự nghĩ từ xưa ko AC thì thôi, htrc lên geeks thấy nộp cx ko AC =))))
(y hệt code bạn lol)
thoi duoc roi, ban co the doc stk ._.
chu co chua moi biet toi sai o dau T_T
thoi anh ạ , e cảm ơn nhưng mà em không lấy đâu anh nhé hihi
ua kb cx dc :)))
bài này sao admin tg ít quá
Anh check bên OJ cũ vẫn có 3 người được AC em ạ :D