Biến đổi mảng bằng phép đổi chỗ kề

greedy
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved