Codeforces 371(#218 Div2 only) A. K-Periodic Array
問題
各要素が1または2の長さnの数列a[i]が与えられる。
与えられたnの約数kについて、a[i]を周期kにするには、a[i]の要素を最低いくつ変更しなければならないか。
制約条件
n, k≦100
a[i]は1または2
方針
iをkで割った余りごとにa[i]をわける。
同じ余りの中で、1, 2の数をそれぞれ数えて、多いほうに小さいほうを変更すればいい。
ソースコード
int n, k, a[100]; int main(){ vi v[100]; int ans = 0; cin >> n >> k; rep(i, n){ cin >> a[i]; v[i % k].pb(a[i]); } rep(i, k){ vi &d = v[i]; map<int, int> cnt; int mx = 0; rep(j, d.size()) cnt[d[j]]++; each(j, cnt) mx = max(mx, j->second); ans += d.size() - mx; } cout << ans << endl; return 0; }