C++ bài 10.C3: Khôi phục hoán vị
Chúng ta có một dãy số \(p = \{p_1, p_2, ..., p_N\}\) là một hoán vị của \(\{1, 2, ..., N\}\).
Bạn có thể thực hiện thao tác sau đây nhiều nhất một lần: chọn các số nguyên \(i\) và \(j\) \((1 \leq i < j \leq N)\), và hoán đổi \(p_i\) và \(p_j\). Lưu ý rằng bạn cũng có thể chọn không thực hiện hoán đổi.
In ra "YES" nếu bạn có thể sắp xếp \(p\) theo thứ tự tăng dần theo cách đã nêu, và "NO" nếu không thể.
Ràng buộc:
- Tất cả giá trị đầu vào là số nguyên.
- \(2 \leq N \leq 50\)
- \(p\) là một hoán vị của \(\{1, 2, ..., N\}\).
ĐỊNH DẠNG ĐẦU VÀO
Đầu vào được cung cấp từ đầu vào chuẩn như sau:
N
p_1 p_2 ... p_N
ĐỊNH DẠNG ĐẦU RA
In ra "YES" nếu có thể sắp xếp \(p\) theo thứ tự tăng dần như đã nói, và "NO" nếu không thể.
Ví dụ:
Input
5
5 2 3 4 1
Output
YES
Bạn có thể sắp xếp \(p\) theo thứ tự tăng dần bằng cách hoán đổi \(p_1\) và \(p_5\).
Input
5
2 4 3 5 1
Output
NO
Trong trường hợp này, hoán đổi bất kỳ hai phần tử nào cũng không thể sắp xếp \(p\) theo thứ tự tăng dần.
Giải thích ví dụ mẫu
Nếu bạn có thể sắp xếp dãy số bằng cách hoán đổi đúng một cặp phần tử, thì sau khi hoán đổi, dãy số sẽ có đúng một hoặc không có phần tử sai thứ tự so với dãy sắp xếp. Nếu không, bạn không thể sắp xếp dãy số bằng một hoán đổi duy nhất.
Lời giải bài tập này: Tại đây
Group giải đáp thắc mắc: Lập trình 24h
Fanpage CLB: CLB lập trình Full House- Việt Nam
Youtube: CLB Lập Trình Full House
Comments