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]);
}
}
}