Sắp xếp mảng bằng một lần đảo đoạn
Đề bài
Mô tả
Cho một mảng gồm số nguyên đôi một phân biệt.
Hãy xác định xem có thể sắp xếp mảng theo thứ tự tăng dần bằng cách đảo ngược đúng một đoạn con hay không.
Đảo ngược đoạn nghĩa là thay dãy bằng dãy (các phần tử còn lại giữ nguyên).
Lưu ý: bạn phải đảo ngược đúng một đoạn. Nếu mảng đã được sắp xếp sẵn, bạn vẫn có thể chọn một đoạn chỉ gồm một phần tử (ví dụ ) — việc đảo ngược đoạn đó không làm thay đổi mảng.
Dữ liệu vào
- Dòng đầu chứa số nguyên — kích thước mảng.
- Dòng thứ hai chứa số nguyên phân biệt .
Dữ liệu ra
In ra yes hoặc no tùy theo câu trả lời.
Nếu câu trả lời là yes, in thêm một dòng chứa hai số nguyên và () là chỉ số đầu và cuối của đoạn cần đảo ngược. Nếu có nhiều cách chọn, in ra bất kỳ cách nào.
Ràng buộc
- Các phần tử đôi một phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 2 1 |
yes 1 3 |
Đảo ngược toàn bộ mảng được 1 2 3 đã sắp xếp. |
| 4 2 1 3 4 |
yes 1 2 |
Đảo ngược đoạn [1, 2] được 1 2 3 4. |
| 4 3 1 2 4 |
no | Không có đoạn nào đảo ngược để mảng được sắp xếp. |
| 2 1 2 |
yes 1 1 |
Mảng đã sắp xếp, đảo một đoạn một phần tử là hợp lệ. |
Bình luận