Hoán vị tuyệt vời nhất
Đề bài
Mô tả
Một hoán vị phần tử là một cách sắp xếp lại số nguyên dương đầu tiên. Ví dụ, với có hoán vị: , , , , và . Một hoán vị tuyệt vời là một hoán vị phần tử có dạng . Nói cách khác, hoán vị tuyệt vời thu được bằng cách chuyển một tiền tố của sang bên phải. Lưu ý rằng cũng là một hoán vị tuyệt vời.
Với một hoán vị, định nghĩa trọng số của nó là số lần ít nhất cần đổi chỗ hai phần tử kề nhau để hoán vị trở thành một hoán vị tuyệt vời.
Ví dụ, trọng số của là , vì có thể biến nó thành hoán vị tuyệt vời sau ít nhất hai lần đổi chỗ:
- Đổi chỗ phần tử thứ và thứ : .
- Đổi chỗ phần tử thứ và thứ : .
Cho một dãy biểu diễn một hoán vị bị mất một số phần tử. Hãy tính trọng số nhỏ nhất trong số tất cả các hoán vị có thể thu được bằng cách thay các phần tử bị mất bằng những giá trị phù hợp. Ví dụ, với dãy , trong đó các số là phần tử bị mất, có hai hoán vị có thể là với trọng số và với trọng số . Vậy trọng số nhỏ nhất là .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm:
- Dòng thứ nhất chứa số nguyên : số phần tử của hoán vị.
- Dòng thứ hai chứa số nguyên cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn thu được ít nhất một hoán vị hợp lệ sau khi thay tất cả các số bằng các giá trị khác.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra kết quả trên một dòng.
Ràng buộc
- .
- .
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 3 2 1 4 4 2 3 0 0 |
2 0 |
Hai bộ dữ liệu chính là hai ví dụ trong đề bài. |
| 5 1 1 1 0 3 0 0 0 5 5 4 3 2 1 5 0 1 0 0 2 |
0 0 0 4 2 |
Với , hoán vị tuyệt vời gần nhất là (hoặc ), cần lần đổi chỗ. Với bộ cuối, điền thành rồi đưa về bằng lần đổi chỗ. |
Bình luận