T1 Attack
1 记录
考场上时懵的,这是个啥?为什么没有部分分?
弃了
Continue reading “中山纪念中学 Day2 2019.08.02”「Jump up HIGH!!」
写在前面 这次是两种大家十分熟悉也是常见的东西,在中间的代码力玩花样的题并非没有,总而言之这是两种十分神奇的算法了qwq
#include <cstdio>
using namespace std;
int n;
int result[110000];
int a[110000];
void marge(int *data,int start,int end,int *result){// 合并区间
int left_start,result_start,right_start;
left_start=result_start=start;
right_start=(start+end+1)/2+1;
while(left_start<=(start+end+1)/2&&right_start<=end){
if(data[left_start]<data[right_start]) result[result_start++]=data[left_start++];
else result[result_start++]=data[right_start++];
}
while(left_start<=(start+end+1)/2) result[result_start++]=data[left_start++];
while(right_start<=end) result[result_start++]=data[right_start++];
}
void margesort(int *data,int start,int end,int *result){// 二分
if(end-start==1){// 刚好差为1,那么这两个相邻,就可以排序
if(data[start]>data[end]){
int temp=data[end];
data[end]=data[start];
data[start]=temp;
}
return ;
}
else if(end-start==0) return ;//相同你排个瓜皮啊
else {
margesort(data,start,(start+end+1)/2,result);//继续二分排序
margesort(data,(start+end+1)/2+1,end,result);
marge(data,start,end,result);// 合并
for(int i=start;i<=end;i++) data[i]=result[i];//排序完的总的回去吧233
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
margesort(a,1,n,result);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
我给你讲这个代码还是压过行的
上面的注释我觉得知道原理估计看不懂,说一下归并排序的原理:
(start+end+1)/2
与(start+end+1)/2+1
是为了什么,可不可以替换?<=
是否可以换成<
#include <cstdio>
using namespace std;
int n;
int a[110000];
void qsort(int *data,int s,int e){
int o_l=s,o_r=e;
int base=data[(s+e)/2];//取中快排
do{
while(data[s]<base) s++;// 比自己大的
while(data[e]>base) e--;//比自己小的
if(s<=e){//上面两个循环都被打断说明顺序不对,交换一下
int temp=data[s];
data[s]=data[e];
data[e]=temp;
s++;
e--;
}
}while(s<=e);
if(o_l<e) qsort(data,o_l,e);//确保不越界
if(s<o_r) qsort(data,s,o_r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
qsort(a,1,n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}