Biến đổi dãy số - LCOJ: Luyện Code Online Judge

EQARR - Biến đổi dãy số

Điểm: 1,00 (OI)

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

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

Tác giả:

siro

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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

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

Please read the guidelines before commenting.

0
0988440189 đã bình luận lúc 2, Tháng 7, 2025, 0:44
Ý tưởng của mình là cứ cho 2 cặp liên tiếp phải bằng nhau rồi xét sang cặp khác -Ban đầu sắp xếp tăng dần

Sau đó so sánh dùng while (a[i]<a[i+1]) thì tăng tất cả phần tử trong mảng trừ phần tử a[i+1] lên 1 đơn vị vì đề bảo là mỗi lần tăng sẽ phải tăng N-1 phần tử Từ {1,2,3}->{2,2,4}->{3,3,4}->{4,4,4} cách này thì bị TLE hết , mọi người có cách nào hay chia sẽ mình với

-2

nqtrung123 đã bình luận lúc 8, Tháng 10, 2024, 11:24 ← sửa 3 →

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

-2

vudinhlong đã bình luận lúc 30, Tháng 9, 2024, 17:53 ← chỉnh sửa →

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 :))

-2

vudinhlong đã bình luận lúc 28, Tháng 6, 2024, 20:23

ai AC đọc stk ._.

-2

vudinhlong đã bình luận lúc 9, Tháng 8, 2024, 13:37

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)