哎看到这题完全没思路,都不晓得怎么动笔
首先k一定是奇数
因为第一次单独的调用merge(0,n)
接下来分成两个子区间,若子区间有序调用0次,无序调用2次
可见k=1+2+2+2+2+2+2…+2
知道这个就好办了,直接模拟merge函数
若当前k还存在,那就交换a[mid-1]和a[mid]使得当前区间无序
但是这样左右两区间内仍然有序,k-=2
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,k,a[maxn]; void merge_sort(int l,int r) { if(r-l<=1) return; if(k) { int mid= l+r>>1; k-=2; swap(a[mid-1],a[mid]); merge_sort(l,mid); merge_sort(mid,r); } } void over(){ cout<<-1; exit(0); } int main() { cin >> n >> k; k--; if( k&1 ) over(); else { for(int i=0;i<n;i++) a[i]=i+1; merge_sort(0,n); if( k ) over(); for(int i=0;i<n;i++) cout<<a[i]<<" "; } }