Thu Thập Số II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một hoán vị của các số $1, 2, \dots, n$ . Bạn cần thu thập các số theo thứ tự tăng dần bằng cách duyệt mảng từ trái sang phải nhiều lượt.

Sau mỗi thao tác hoán đổi hai vị trí trong mảng, hãy in ra số lượt tối thiểu cần thiết để thu thập tất cả các số.

Dòng 1: hai số nguyên $n$ và $m$
Dòng 2: $n$ số nguyên — hoán vị của $1, 2, \dots, n$
$m$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a$ và $b$ — hoán đổi phần tử tại vị trí $a$ và vị trí $b$

In ra $m$ số nguyên — mỗi dòng là số lượt cần thiết sau thao tác tương ứng.

Input	Output	Giải thích
5 3 4 2 1 5 3 2 3 1 5 2 3	2 3 4	Sau hoán đổi đầu tiên mảng là [4,1,2,5,3], cần 2 lượt.
4 2 2 1 3 4 1 2 3 4	1 2	Hoán đổi vị trí 1,2: [1,2,3,4] cần 1 lượt.

Bình luận

Không có bình luận tại thời điểm này.