C bài 13.E3: Biến đổi số
Có một dãy số có độ dài \(N: A_1, A_2, ..., A_N\).
Snuke có thể thực hiện thao tác sau trên dãy số này:
- Chọn \(K\) phần tử liên tiếp trong dãy số. Sau đó, thay giá trị của từng phần tử đã chọn bằng giá trị nhỏ nhất trong số các phần tử đã chọn.
Snuke muốn làm cho tất cả các phần tử trong dãy số trở nên giống nhau bằng cách lặp lại thao tác trên một số lần. Hãy tìm số lần thao tác ít nhất cần thiết để đạt được mục tiêu này. Dưới các ràng buộc của bài toán, luôn có thể thực hiện được mục tiêu này.
INPUT FORMAT
Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(K\) \((2 \leq K \leq N \leq 10^6)\).
Dòng thứ hai gồm một dãy \(a\) gồm \(N\) số nguyên dương \((1 \leq a_i \leq 10^6)\).
OUTPUT FORMAT
In ra số thao tác tối thiểu Snuke cần để làm cho dãy trở nên giống nhau.
Ví dụ 1:
Input
4 3
2 3 1 4
Output
2
Ví dụ 2:
Input
3 3
1 2 3
Output
1
Giải thích ví dụ mẫu
Ví dụ 1:
- Input:
4 3
- Giải thích: Cần 2 thao tác để biến dãy thành giống nhau, đầu tiên là chọn 3 phần tử đầu, sau đó chọn lại.
Ví dụ 2:
- Input:
3 3
- Giải thích: Chỉ cần 1 thao tác để làm tất cả các phần tử giống nhau bằng cách chọn toàn bộ dãy.
Lời giải bài tập này: Tại đây
Group giải đáp thắc mắc: Lập trình 24h
Fanpage CLB: CLB lập trình Full House- Việt Nam
Youtube: CLB Lập Trình Full House
Comments