Sắp xếp kỳ lạ
Đề bài
Mô tả
Cho một mảng gồm phần tử.
Bạn được cho một tập hợp gồm vị trí phân biệt với . Vị trí có nghĩa là bạn được phép hoán đổi hai phần tử và . Bạn có thể thực hiện thao tác này bao nhiêu lần tùy ý với mỗi vị trí trong tập.
Hãy xác định xem có thể sắp xếp mảng ban đầu theo thứ tự không giảm () chỉ bằng các phép hoán đổi được phép hay không.
Có bộ dữ liệu độc lập cần trả lời.
Dữ liệu vào
- Dòng đầu chứa một số nguyên () là số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm ba dòng:
- Dòng đầu chứa hai số nguyên và ().
- Dòng thứ hai chứa số nguyên ().
- Dòng thứ ba chứa số nguyên phân biệt ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra YES nếu có thể sắp xếp mảng theo thứ tự không giảm bằng các phép hoán đổi được phép, ngược lại in ra NO.
Ràng buộc
- , các phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 3 2 3 2 1 1 2 4 2 4 1 2 3 3 2 5 1 1 2 3 4 5 1 4 2 2 1 4 3 1 3 4 2 4 3 2 1 1 3 5 2 2 1 2 3 3 1 4 |
YES NO YES YES NO YES |
Bộ 1: , . Đổi vị trí 2: , đổi vị trí 1: , đổi vị trí 2: . Bộ 2: với , không thể đưa số về đầu vì vị trí 1 không được phép, nên không sắp xếp được. |
| 1 4 2 2 4 1 3 1 3 |
NO | Chỉ được đổi cặp (1,2) và cặp (3,4). Đoạn đầu đã tăng, đoạn sau đã tăng, nhưng vị trí 3 (giá trị ) và vị trí 4 (giá trị ) không thể vượt qua nhau vì vị trí 2 không được phép hoán đổi. |
Bình luận