C++ bài 10.C3: Khôi phục hoán vị


Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 20M

Author:
Problem type

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

There are no comments at the moment.

Zalo