归并排序的逆操作,每次二分时把第二段第一位与第一段最后一位开始往前第一个比它大的数交换位置

可以用归并排序验证答案对不对

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; int a[N],b[N],k,res;
void rmergesort(int l,int r)
{
if(l==r||k<=)return ;
k-=;
int m=(l+r)>>;
if((r-l)%==)m--;
// cout<<l<<" "<<m<<" "<<r<<endl;
int ans=a[m+],id=m+;
for(int i=m;i>=l;i--)
{
if(ans>a[i])
{
ans=a[i];
id=i;
break;
}
}
swap(a[id],a[m+]);
rmergesort(l,m);
rmergesort(m+,r);
}
void mergesort(int l,int r)
{
res++;
bool f=;
for(int i=l+;i<=r;i++)
{
if(a[i]<a[i-])
{
f=;
break;
}
}
if(!f)return ;
int m=(l+r)>>;
if((r-l)%==)m--;
mergesort(l,m);
mergesort(m+,r);
int p1=l,p2=m+,i=l;
while(i<=r)
{
if(p1>m)b[i]=a[p2++];
else if(p2>r)b[i]=a[p1++];
else
{
if(a[p1]>a[p2])b[i]=a[p2++];
else b[i]=a[p1++];
}
i++;
}
for(int i=l;i<=r;i++)
a[i]=b[i];
}
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)a[i]=i;
k--;
rmergesort(,n);
if(k!=)puts("-1");
else
{
for(int i=; i<=n; i++)
printf("%d ",a[i]);
puts("");
}
/* res=0;
mergesort(1,n);
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
puts("");
cout<<k<<" "<<res<<endl;*/
return ;
}
/******************** ********************/

最新文章

  1. HDU--杭电--1026--Ignatius and the Princess I--广搜--直接暴力0MS,优先队列的一边站
  2. java 堆栈分析4
  3. Java 关键字 native
  4. UNIX网络编程
  5. UVa 540 (团体队列) Team Queue
  6. 如何获取、下载、安装fortran编译工具ifort
  7. Nodejs随笔(三):全局对象之global
  8. Maven:常用命令
  9. CountDownLatch和CyclicBarrier 区别
  10. echarts-for-react 从新渲染数据
  11. postman测试请求参数中文乱码问题
  12. JAVA对Excel的导入导出
  13. poj3278 【BFS】
  14. sqlserver常用调优脚本
  15. 优秀的第二外语学习网站:Lang-8
  16. SharePoint2013使用资源管理器打开失败
  17. 浏览器Request Header和Response Header的内容
  18. UVAL 7902 2016ECfinal F - Mr. Panda and Fantastic Beasts
  19. 分布式之zk的应用场景
  20. JAVA消息 AMQP

热门文章

  1. mysql导出数据库提示警告在GTID模式下面
  2. LNMP环境搭建之php安装,wordpress博客搭建
  3. 蒙特卡洛方法计算圆周率的三种实现-MPI openmp pthread
  4. window安装redis
  5. Linux下apache安装php
  6. RedisTemplate访问Redis数据结构(介绍和常用命令)
  7. nginx学习之详细安装篇(二)
  8. iphone传感器
  9. php在不同平台下路径分隔符不同的解决办法
  10. Django与Vue语法冲突问题完美解决方法