Educational Codeforces Round 30D. Merge Sort
2024-09-06 15:56:54
归并排序的逆操作,每次二分时把第二段第一位与第一段最后一位开始往前第一个比它大的数交换位置
可以用归并排序验证答案对不对
#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 ;
}
/******************** ********************/
最新文章
- HDU--杭电--1026--Ignatius and the Princess I--广搜--直接暴力0MS,优先队列的一边站
- java 堆栈分析4
- Java 关键字 native
- UNIX网络编程
- UVa 540 (团体队列) Team Queue
- 如何获取、下载、安装fortran编译工具ifort
- Nodejs随笔(三):全局对象之global
- Maven:常用命令
- CountDownLatch和CyclicBarrier 区别
- echarts-for-react 从新渲染数据
- postman测试请求参数中文乱码问题
- JAVA对Excel的导入导出
- poj3278 【BFS】
- sqlserver常用调优脚本
- 优秀的第二外语学习网站:Lang-8
- SharePoint2013使用资源管理器打开失败
- 浏览器Request Header和Response Header的内容
- UVAL 7902 2016ECfinal F - Mr. Panda and Fantastic Beasts
- 分布式之zk的应用场景
- JAVA消息 AMQP