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.

Author: bedao

Gọi hai chữ cái xuất hiện trong hai xâu đã cho lần lượt là AB.

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

Please read the guidelines before commenting.


There are no comments at the moment.