CodeForces 873D Merge Sort 构造 分治

题意

给出一个归并排序的算法\(mergesort\)，如果对于当前区间\([l, r)\)是有序的，则函数直接返回。

否则会分别调用\(mergesort(l, mid)\)和\(mergesort(mid, r)\)，其中\(mid = \left \lfloor \frac{l+r}{2} \right \rfloor\)

最后合并左右两个子区间

下面请你构造一个\(1 \sim n\)的排列，并且恰好调用\(k\)次\(mergesort\)函数完成排序

分析

首先，对函数的调用次数一定是奇数次

因为除去最开始对函数的调用，之后每次调用函数都是对左右区间成对调用的

设一开始排列\(p\)是从\(1\)到\(n\)的顺序排列

模拟\(mergesort\)函数的调用进行构造，假设当前区间为\([l,r),(r-l>1)\)，并且当前调用次数未满\(k\)次

那么 交换\(p[mid-1]\)和\(p[mid]\)，则区间\([l,r)\)变为无序，函数调用次数增加\(2\)

而 左右两个子区间仍然是有序的 ，不断递归进行处理直到调用次数等于\(k\)或对所有区间处理完毕

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)

const int maxn = 100000 + 10;

int n, k;

int a[maxn];

void solve(int l, int r) {

	if(!k || r - l == 1) return;

	k--;

	int mid = (l + r) / 2;

	swap(a[mid], a[mid - 1]);

	solve(l, mid);

	solve(mid, r);

}

int main() {

	scanf("%d%d", &n, &k);

	k--;

	if(k & 1) { printf("-1\n"); return 0; }

	k >>= 1;

	REP(i, 0, n) a[i] = i + 1;

	solve(0, n);

	if(k) printf("-1\n");

	else REP(i, 0, n) printf("%d ", a[i]);

	printf("\n");

	return 0;

}