Editorial for Bedao Mini Contest 15 - SEQGAME2


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Với mỗi vị trí i có ~ 1 \le a[i] \le N~ ta tính ~F[i]~ là số lần dịch chuyển cần thiết để đưa ~a[i]~ về đúng vị trí .

Ta có ~cnt[x]~ là số lượng vị trí ~i~ mà có ~F[i] = x~.

Nhận thấy rằng các thao tác biến đổi không ảnh hướng đến nhau. Giả sử ta thực hiện ~x~ lần dịch phải, thì số thao tác cần thiết để biến đổi dãy về dạng ~1 , 2 , ... , N~ là ~x + n - cnt[x]~.

Ta dùng set để lưu lại các giá trị ~ x - cnt[x]~ , tìm giá trị nhỏ nhất để bước biến đổi là min.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.