Biến đổi mảng bằng phép đổi chỗ kề
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho hai mảng $A$ và $B$ cùng độ dài $N$, trong đó $B$ là một hoán vị của $A$ (các phần tử có thể trùng nhau). Mỗi bước, bạn được phép chọn hai phần tử đứng kề nhau trong mảng $A$ và đổi chỗ chúng. Hãy tìm số bước ít nhất để biến đổi mảng $A$ thành mảng $B$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$.
- Dòng thứ hai chứa $N$ số nguyên của mảng $A$.
- Dòng thứ ba chứa $N$ số nguyên của mảng $B$.
Dữ liệu ra
In ra số phép đổi chỗ kề ít nhất cần thực hiện.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 1 3 2 2 3 1 2 1 |
4 |
Giới hạn
- $1 \le N \le 10^5$
- $-10^9 \le A[i], B[i] \le 10^9$
Community Discussion