Hoán đổi chẵn và lẻ
Submit solution
Points:
3
Time limit:
1.0s
Memory limit:
488M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho hai dãy số a và b có độ dài n, dãy a bao gồm các số lẻ phân biệt trong phạm vi [1, 2n], dãy b bao gồm các số chẵn phân biệt trong phạm vi [1, 2n].
Bạn có thể chọn phần tử thứ i nào đó trong 2 mảng và hoán đổi nó với phần tử thứ i+1 trong mảng đã chọn.
Hãy tính số lần hoán đổi nhỏ nhất để khiến mảng a nhỏ hơn mảng b.
Biết rằng, với 2 mảng a, b cùng độ dài, mảng a nhỏ hơn mảng b khi tại vị trí phần tử đầu tiên a và b khác nhau, phần tử đó của mảng a nhỏ hơn b.
Input
- Đầu vào là số lượng test case t (1 <= t <= 1e4), sau đó đến độ dài n (1 <= n <= 1e5), tiếp đó là 2 dãy a và b (1 <= ai <= 2n, 1<= bi <=2n).
Output
- Với mỗi test, in ra một số duy nhất là số lần hoán đổi nhỏ nhất để khiến mảng a nhỏ hơn mảng b.
Example
Input 1
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8Output 1
0
2
3Giải thích:
Ở test case 1, dãy a đã nhỏ hơn dãy b nên không cần hoán đổi.
Ở test case 2, một trong những phương án khả thi là swap 3 với 5 và swap 2 với 4.
Comments
monotonic stack
mỗi ngày một phương pháp mới :v
Bài này nhanh nhất thì chắc có lẽ dùng mảng đánh dấu là đúng bài :vvvv
chặt nhị phân :))