#1479. PSWAP - Đổi chỗ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một hoán vị h_1, h_2, \ldots, h_n là một hoán vị của 1, 2, \ldots, n , bạn được thực hiện hai loại phép biến đổi sau:

  • Chọn hai phần tử bất kì và tráo đối, loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần;
  • Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa hoán vị h_1, h_2, \ldots, h_n thành hoán vị 1, 2, \ldots, n .

Dữ liệu vào:

  • Dòng đầu chứa số nguyên n ;
  • Dòng thứ hai chứa n số nguyên h_1, h_2, \ldots, h_n là một hoán vị của 1, 2, \ldots, n .

Dữ liệu ra:

  • Ghi ra thiết bị ra chuẩn một số nguyên là số phép biến đổi ít nhất để đưa hoán vị h_1, h_2, \ldots, h_n thành hoán vị 1, 2, \ldots, n .

Ví dụ:

Dữ liệu vào:

5
5 3 4 2 1

Dữ liệu ra:

3

Giới hạn:

  • 10\% số test ứng với 10\% số điểm của bài có n = 3 ;
  • 20\% số test khác ứng với 20\% số điểm của bài có n \le 30 ;
  • 20\% số test khác ứng với 20\% số điểm của bài có n \le 300 ;
  • 20\% số test khác ứng với 20\% số điểm của bài có n \le 1000 ;
  • 15\% số test khác ứng với 15\% số điểm của bài có n \le 10^4 ;
  • 15\% số test còn lại ứng với 15\% số điểm của bài có n \le 10^5 .