Educational Codeforces Round 30 D. Merge Sort
2024-10-17 21:58:51
题意:给你n和k,n代表有多少个数,k代表几次操作,求一个1到n的序列,要k次mergesort操作才能还原
Examples
Input
3 3
Output
2 1 3
Input
4 1
Output
1 2 3 4
Input
5 6
Output
-1 思路:看了很久才看懂题目的意思,根据题意对于一个[l,r)的区间,如果是乱的,你会先mergesort一下,如果已经是递增的,
那么就不用继续往下操作了;如果不是递增的,那么就要分一下,对左边[l,mid)操作,右边[mid,r)操作,等到左边和
右边的都排完,然后最后再排一下,这样的操作次数是2。所以对于每一个样例,k肯定是个奇数,因为你最开始要操作一
次全区间,然后才开始递归,而且k不会大于等于2*n,因为全部分开,操作最多也就是2*n-1(自己画一下图就知道了)。
我们就从末状态开始,往前走,每次dfs把a[mid]和a[mid-1]换一下,因为a[mid-1]是在左边区间的,a[mid]是在右
边区间的,所以你需要左边排一下,右边排一下,这样操作次数是2,最后排一下,就是这个最后排一下,可以把我们交换
的还原(我猜应该是这样233333)。细节就看代码吧。 代码:
#include<iostream>
#include<string.h>
using namespace std; const int maxn=1e5+5; int a[maxn],n,k; void dfs(int l,int r){
if(k==1||r<=l+1)return ;
k-=2;
int mid=(l+r)/2;
int x=a[mid];
a[mid]=a[mid-1]; a[mid-1]=x;
//因为左边的区间是[l,mid),右边的区间是[mid,r),所以应该要把a[mid-1]和a[mid]换一下
//这样就需要两次mergesort才能还原,(一次左边,一次右边,最后总的一次还原)
dfs(l,mid);
dfs(mid,r);
}
int main(){
cin>>n>>k;
if(k>=2*n||k%2==0){
cout<<-1<<endl;
return 0;
}
for(int i=1;i<=n;i++)a[i]=i;
dfs(1,n+1);
for(int i=1;i<=n;i++){
if(i!=1)cout<<' ';
cout<<a[i];
}
cout<<endl;
return 0;
}
最新文章
- EntityFrame Work 6 Code First 配置字段为varchar 类型
- iphone 群发短信 闪退 彻底解决
- 基于Maven引入Hadoop包报Missing artifact jdk.tools:jdk.tools:jar:1.6
- SQL、LINQ、Lambda 三种用法(转)
- CSS3_边框属性之圆角的基本图形案例
- Lua中cJson的读写
- 尝试封装自己的js库
- C程序设计语言练习题1-8
- wordpress常用插件汇总
- configparser_配置解析器
- 《通过C#学Proto.Actor模型》之Supervision
- RestFramework自定制之认证和权限、限制访问频率
- VK Cup 2016 - Qualification Round 2 B. Making Genome in Berland
- XML解析之JAXP
- ABP .Net Core To Json序列化配置
- 前端程序员经常忽视的一个 JavaScript 面试题
- Go语言Web框架gwk介绍 (二)
- (一)Linux实操之——权限、任务调度、磁盘分区
- 对字符串进行base64加解密---基于python
- HDU 4514 湫湫系列故事――设计风景线 (树形DP)