D. Merge Sort（分治||构造）

https://codeforces.com/contest/873/problem/D
题意：
构造一个1到n的排列，使的这个排列进行归并排序时，递归的次数为k。

思路：考虑题目给出的过程，排序时无论(0,n)是否有序都会进行一次，接下来，会把一个区间分成两个，重复该过程，所以k一定为奇数。
构建过程，考虑分治，每次分成两个区间，k就会减少2，那么k!=0时这些区间都是逆序的，直接从大到小赋值，k=0时就按照顺序构造，那么当前l,r的值就是顺序，从小到大，注意这个从小到大是当前k=0的区间

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define fi first
#define se second
#define show(a) cout<<a<<endl;
#define show2(a,b) cout<<a<<" "<<b<<endl;
#define show3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl;
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> LP;
const ll inf = 1e17 + 10;
const int N = 3e6 + 10;
const ll mod = 10007;
const int base=131;
tr1::unordered_map<ll,ll> mp;

ll n,m,id,x,y,k,q;
ll num[N],vis[N],cnt;
ll a[N],b[105][105],c[105][105];
ll ans,flag,sum;
//ll tree[N],tag[N];
set<ll> st;
vector<ll> v;
string s;

void dfs(int l,int r)
{
	if(k==0)
	{
		int t=cnt-(r-l)+1;
		cnt=t-1;
		for(int i=l;i<r;i++)
		{
			a[i]=t++;
		}
		return ;
	}
	if(l==r-1)
	{
		a[l]=cnt--;
		return ;
	}
	k-=2;
	int mid=l+r>>1;
	dfs(l,mid);
	dfs(mid,r);

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>k;
	if(k%2==0) cout<<-1;
	else
	{
		k--;
		cnt=n;
		dfs(0,n);
		if(k==0)
		{
			for(int i=0;i<n;i++) cout<<a[i]<<" ";
		}
		else cout<<-1;
	}
}

最后

以上就是俊逸翅膀为你收集整理的D. Merge Sort（分治||构造）的全部内容，希望文章能够帮你解决D. Merge Sort（分治||构造）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。