CS Academy 050 Div.2 E. Min Swaps

CS Academy 050 Div.2 E. Min Swaps

CS Academy

感想

見掛け倒しな感じがある。

解法

まず値が大きいものと小さいものが順に現れるように順列を作れば、なんとなく条件を満たしそうなことから、そのように並べてみる。

その数列が小さいものからスタートすると考え、$\ a_1, a_2, a_3, ..., a_n\ $となったとすると、この数列のコストは、$\ (a_2 - a_1) + (a_2 - a_3) + ... + (a_{n - 2} - a_{n - 1}) + (a_n - a_{n - 1})\ $、すなわち$\ -a_1 + 2 * (a_2 + a_4 + ... ) - 2 * (a_3 + a_5 + ... ) + a_n\ $となる。よって$\ a_1\ $が小さいものの中で最大のもの、$\ a_n\ $が大きいものの中で最小となっていればよい。つまり、$\ a_1 = \frac {n} {2},\ a_n = \frac {n} {2} + 1\ $としておけばよい。

あとは偶数番目の位置に何個の小さい数が入っているかを数えれば、必要なスワップの回数が求められる。

実装

#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

int get(int n, vector<int> a) {
        int res = 0;
        if (a[0] != n / 2) {
                res ++;
                for (int i = 0; i < n; i ++) if (a[i] == n / 2) swap(a[0], a[i]);
        }
        if (a[n - 1] != n / 2 + 1) {
                res ++;
                for (int i = 0; i < n; i ++) if (a[i] == n / 2 + 1) swap(a[n - 1], a[i]);
        }
        for (int i = 1; i < n - 1; i += 2) if (a[i] < n / 2) res ++;
        return res;
}

void solve() {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        int ans = get(n, a);
        reverse(all(a));
        ans = min(ans, get(n, a));
        cout << ans << endl;
        return;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t --) solve();
        return 0;
}