Editorial for Bedao Regular Contest 04 - ACCIO
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Gọi hai chữ cái xuất hiện trong hai xâu đã cho lần lượt là A
và B
.
Dễ thấy độ dài hai xâu phải bằng nhau và số lần xuất hiện của A
trong hai xâu đã cho phải bằng nhau. Nếu không đáp án sẽ là ~-1~.
Gọi các vị trí xuất hiện của A
trong xâu ~s~ là ~x_1, x_2, \ldots, x_k~ và trong xâu ~t~ là ~y_1, y_2, \ldots, y_k~.
Đáp án của bài toán là ~\sum\limits_{i = 1}^{k} |x_i - y_i|~.
Dễ thấy đây là đáp án bé nhất có thể (không có bước nào thừa - đổi chỗ hai kí tự A
). Ta có thể tạo dãy các bước di chuyển như sau để đạt đáp án tối ưu:
- Nếu tồn tại ~i~ sao cho ~x_i > y_i~: Gọi ~p~ là giá trị bé nhất sao cho ~x_p > y_p~. Ta sẽ sử dụng ~x_q - y_q~ bước để di chuyển cho chúng đúng vị trí.
- Nếu không: Gọi ~q~ là giá trị lớn nhất sao cho ~x_q < y_q~. Ta sẽ sử dụng ~y_q - x_q~ bước để di chuyển cho chúng đúng vị trí.
Comments