构造+模拟，CF 873D - Merge Sort
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
873D - Merge Sort
二、解题报告
1、思路分析
考虑初始会调用一次，然后每次分治又会增加两次，所以一定会调用奇数次
k 为偶数直接特判
然后我们模拟归并的过程，由于归并的前提是存在逆序对，那么我们将左边最大和右边最小调换位置然后分治递归即可
2、复杂度
时间复杂度： O(nlogn)空间复杂度：O(n)
3、代码详解
#include <bits/stdc++.h>
// #define DEBUG
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
void solve(){
int n, k;
std::cin >> n >> k;
if (k % 2 == 0) {
std::cout << -1;
return;
}
std::vector<int> a(n);
std::iota(a.begin(), a.end(), 1);
// [l, r)
auto dfs = [&](auto &&self, int l, int r) -> void {
if (k == 0 || l + 1 == r) return;
int m = (l + r) / 2;
k -= 2;
std::swap(a[m - 1], a[m]);
self(self, l, m);
self(self, m, r);
};
-- k;
dfs(dfs, 0, n);
if (k) std::cout << -1;
else for (int x : a) std::cout << x << ' ';
}
auto FIO = []{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
int main() {
#ifdef DEBUG
freopen("in.txt", 'r', stdin);
freopen("out.txt", 'w', stdout);
#endif
int t = 1;
// std::cin >> t;
while(t --)
solve();
return 0;
}