Description

给定一个从1到n的排列a，要求改动排列中所有元素的下标。

每个元素的下标改动将产生贡献，求最小的贡献之和的一种排列方式。

说明：假设改动前元素位于下标i，改动后位于j，那么贡献为∣i−j∣。

Constraints

  • 3≤n≤2⋅105
  • 1≤ai≤109

Solution

简单构造：

  • 假设n为偶数，显然两两对调改动最小，每个元素贡献1。
  • 假设n为奇数，抽出前n−3个元素做上述偶数处理，最后3个元素贡献4。

没留意数据范围，我还多写了n≤2的情况，问题不大。

Code

#include <bits/stdc++.h>
using namespace std;
namespace vs = views;

int main() {
    int T; cin >> T;
    for(auto _ : vs::iota(0, T)) {
        int n; cin >> n;
        vector<int> a(n);
        ranges::for_each(a, [t=1](auto &v) mutable {v = t++;});

        shared_ptr<void> guard (nullptr, [&](auto) {
            for(auto &&v : a) cout << v << ' ';
            cout << endl;
        });

        if(n <= 2) {
            swap(a.front(), a.back());
            continue;
        }

        auto pivot = (n & 1) ? n - 3 : n;
        for(auto i = 0; i < pivot; i += 2) {
            swap(a[i], a[i+1]);
        }
        if(pivot != n) {
            swap(a[pivot], a[pivot+1]);
            swap(a[pivot+1], a[pivot+2]);
        }
    }
}

Codeforces-1541A Pretty Permutations