笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 AT4431 【[ARC103A] /\/\/\/】

posted on 2020-03-20 11:40:16 | under 题解 |

比较常规的最优化题目。不难发现如果某个数出现次数很多,就要用这个去替换别的数而不是被换掉。所以不难想到分别拿桶记录奇偶位置的出现次数,然后两个都选最多的即可。

然而显然这个做法是不对的。因为限制了必须有两种数字,所以奇偶位置的取值必须不同。定一找二即可。

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 ;
}