Bình luận

• 
  

  -8

  

  ngoccaidu2008  đã bình luận lúc 18, Tháng 9, 2025, 15:18

  Subtask 2:

  Tại mỗi bước để biến đổi từ b[i-1] thành b[i] chúng ta có hai lựa chọn:

  Lựa chọn 1: Chỉ dùng thao tác 1

  • Ta tăng a liên tục cho đến khi bằng b[i].
  • Số thao tác cần dùng là tt1=(b[i]-b[i-1]+m) % m.

  Lựa chọn 2: Dùng thao tác 2

  • Dùng 1 thao tác gán a=X.
  • Từ X ta xem chạm đến b[i] cần bao nhiêu thao tác biến đổi. Số thao tác cho bước này là tt2=1+(b[i]-X+m) % m.

  Số thao tác biến đổi ít nhất là s=min(tt1,tt2)

  Như vậy ta cần tìm giá trị X sao cho tối ưu nhất. Vì m,n<=1000 lên có thể duyệt trâu thử X với từng trường hợp của b[i]

  Độ phức tạp:O(n*m)

  *muốn giải được subtask 1 và 3 thì ib Facebook *

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.