はまやんはまやんはまやん

hamayanhamayan's blog

Alternant Array [CSAcademy #61 B]

https://csacademy.com/contest/round-61/task/alternant-array/

N個の0とN個の1から成る2N個の配列がある。
これを任意回スワップして、10101010...か01010101...にする最小スワップ回数は?

解法

スワップする回数は相違個数/2となる。
そのため、101010...の場合と01010101...の場合についてそれぞれスワップ回数を求めて、小さい方を答える。
(相違個数: A[i] != B[i]となる個数)

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    N *= 2;
    rep(i, 0, N) cin >> A[i];

    int ans = 101010;
    int sm = 0;

    sm = 0;
    rep(i, 0, N) if (A[i] != (i % 2)) sm++;
    ans = min(ans, sm / 2);

    sm = 0;
    rep(i, 0, N) if (A[i] == (i % 2)) sm++;
    ans = min(ans, sm / 2);

    cout << ans << endl;
}