首頁  題目列表  狀態列表  排行榜  註冊  帳號: 密碼:
公告:支援C++11 (2014/08/18 21:39)
Problem 0120 : 蘿莉交換問題
0120 -- 蘿莉交換問題
Case Time Limit: 1500 ms    Memory Limit: 32768 KB
Total Testdata Count: 20
AC/Submit: 9/48    AC/Submit Users: 8/10

[回到列表]
題目敘述

你,もも,是個豢養蘿莉的變態。
有一天你決定要把一半的蘿莉送給你的好朋友
於是你莫名其妙的把你豢養的蘿莉排成兩排,像小學生去升旗那樣
然後你要把這兩排蘿莉分別送給你的兩個好朋友
可是你的好朋友是個追求新奇的人,所以他不希望他擁有兩個屬性一樣的蘿莉
於是為了方便你可以交換兩個同列的蘿莉使得同一排的蘿莉兩兩不相同
因為你還有很多事情要做所以你希望可以用最少次的交換達到目的達到目的

輸入說明

第1行輸入一個$N(\leq 50000)$代表一排的蘿莉數量。
第2行輸入$N$個正整數$x_i(1 \leq x_i \leq 10^5)$代表該蘿莉屬性的hash值
第3行輸入$N$個正整數$y_i(1 \leq y_i \leq 10^5)$代表該蘿莉屬性的hash值

輸出說明

輸出一個正整數代表最少的交換次數

測資保證絕對有辦法可以把蘿莉安排得當

範例輸入

9
2 5 5 2 7 4 7 3 9
1 6 8 4 6 3 9 1 8


範例輸出

3


備註

對於範測,只要交換第1, 3, 5列即可達成條件。



測資組$A$:$N \leq 500$
測資組$B$:$N \leq 5000$
測資組$C$:$N \leq 50000$

測資

測資組A : 1~7 (7筆測資),20 分
測資組B : 8~10 (3筆測資),30 分
測資組C : 11~20 (10筆測資),50 分
[回到列表]