Phân tích

Cho một dãy các số phân biệt, chúng ta được yêu cầu sắp xếp lại nó bằng cách sử dụng một loạt các phép hoán đổi các phần tử kề nhau để tạo thành một dãy lên và xuống. Chúng ta muốn thực hiện sao cho tổng số phép hoán đổi là tối thiểu.

Chúng tôi mô tả một giải pháp tham lam. Chúng tôi sử dụng dãy ví dụ 6, 5, 1, 4, 2, 3 để giúp giải thích giải pháp.

• Lặp lại \(N\) lần:
  • Chọn giá trị nhỏ nhất trong dãy. Trong dãy ví dụ, đó là 1.
  • Xác định xem giá trị nhỏ nhất đó gần đầu bên trái của dãy hơn hay đầu bên phải của dãy hơn. Trong ví dụ, đầu bên trái là nơi có số 6 và đầu bên phải là nơi có số 3. Giá trị nhỏ nhất, 1, gần đầu bên trái hơn (cách 2 phép hoán đổi) so với đầu bên phải (cách 3 phép hoán đổi).
  • Di chuyển giá trị nhỏ nhất về phía đầu gần hơn bằng cách hoán đổi với các phần tử kề nhau, và ghi lại số lượng phép hoán đổi. Trong ví dụ, chúng ta di chuyển 1 về phía 6, đầu tiên hoán đổi 1 và 5, sau đó hoán đổi 1 và 6 dẫn đến dãy: 1, 6, 5, 4, 2, 3. Chúng ta đã thực hiện 2 phép hoán đổi.
  • Loại bỏ số nhỏ nhất khỏi dãy. Trong ví dụ, chúng ta loại bỏ 1 dẫn đến dãy 6, 5, 4, 2, 3.
  • Lặp lại quá trình trên dãy kết quả. Trong ví dụ của chúng ta, chúng ta lặp lại quá trình trên dãy 6, 5, 4, 2, 3. Chúng ta xác định phần tử nhỏ nhất, là 2, sau đó di chuyển nó về phía đầu gần hơn là đầu bên phải với 1 phép hoán đổi, sau đó loại bỏ 2 dẫn đến dãy 6, 5, 4, 3. Sau đó chúng ta lặp lại quá trình cho dãy này. Đầu tiên chọn giá trị nhỏ nhất là 3. Vì 3 đã ở đầu ngoài cùng bên phải, chúng ta thực hiện 0 phép hoán đổi để di chuyển nó đến đầu gần hơn, sau đó chúng ta loại bỏ 3. Chúng ta lặp lại quá trình tương tự cho các giá trị 4, 5, và cuối cùng là 6.
• Cuối cùng, báo cáo tổng số phép hoán đổi. Trong ví dụ của chúng ta, chúng ta đã thực hiện 2 + 1 = 3 phép hoán đổi.

Đó là tất cả! Bạn có thể tự hỏi tại sao thuật toán tham lam lại hoạt động. Chúng tôi đưa ra một trực giác ở đây. Tại mỗi bước trong thuật toán, chúng ta chọn số nhỏ nhất. Trong dãy lên và xuống cuối cùng, số nhỏ nhất này sẽ cần phải đi đến một trong hai đầu tại một thời điểm nào đó. Chúng ta di chuyển số nhỏ nhất này đến đầu gần hơn để tối thiểu hóa số lượng phép hoán đổi. Sau khi số nhỏ nhất này chạm đến đầu gần hơn, vị trí của nó là cố định, tức là vị trí của nó trong dãy lên và xuống cuối cùng đã được thiết lập, do đó nó sẽ không bao giờ cần phải di chuyển/hoán đổi thêm nữa. Vì vậy, trong bước tiếp theo, chúng ta có thể loại bỏ số nhỏ nhất đó khỏi sự cân nhắc và làm việc trên một dãy hoàn toàn mới có kích thước nhỏ hơn một đơn vị. Chúng ta lặp lại quá trình cho dãy mới này, tức là di chuyển phần tử nhỏ nhất đến đầu gần hơn, sau đó loại bỏ số đó, cho đến khi chúng ta đạt được dãy rỗng. Vì chúng ta thực hiện số lượng hoán đổi tối thiểu trong mỗi bước trên mỗi bài toán con (dãy có kích thước nhỏ hơn 1), chúng ta tối thiểu hóa số lượng hoán đổi cho toàn bộ bài toán.

Dựa trên phân tích chính thức của Google Code Jam.