Description

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

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

说明:假设改动前元素位于下标\(i\),改动后位于\(j\),那么贡献为\(\mid i-j \mid\)。

Constraints

  • \(3 \le n \le 2 \cdot 10^5\)
  • \(1 \le a_i \le 10^9\)

Solution

简单构造:

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

没留意数据范围,我还多写了\(n \le 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