比较常规的最优化题目。不难发现如果某个数出现次数很多,就要用这个去替换别的数而不是被换掉。所以不难想到分别拿桶记录奇偶位置的出现次数,然后两个都选最多的即可。
然而显然这个做法是不对的。因为限制了必须有两种数字,所以奇偶位置的取值必须不同。定一找二即可。
```cpp
const int N = 200010 ;
int n ;
int res ;
int ans ;
int t[N] ;
int s[N] ;
int _odd[N] ;
int _eve[N] ;
int base[N] ;
bool compo(int x, int y){
return _odd[x] > _odd[y] ;
}
bool compe(int x, int y){
return _eve[x] > _eve[y] ;
}
int main(){
cin >> n ; res = n ;
for (int i = 1 ; i <= n ; ++ i){
cin >> base[i] ;
if (i & 1) _odd[base[i]] ++ ;
else _eve[base[i]] ++ ;
}
for (int i = 1 ; i < N ; ++ i) s[i] = t[i] = i ;
sort(s + 1, s + N, compo) ;
sort(t + 1, t + N, compe) ;
ans = n / 2 - _odd[s[1]] ;
for (int i = 1 ; i < N ; ++ i)
if (t[i] != s[1]){ ans += n / 2 - _eve[t[i]] ; break ; }
res = min(res, ans) ;
ans = n / 2 - _eve[t[1]] ;
for (int i = 1 ; i < N ; ++ i)
if (s[i] != t[1]){ ans += n / 2 - _odd[s[i]] ; break ; }
res = min(res, ans) ;
cout << res << endl ; return 0 ;
}
```
#