比赛 |
noip2016普及练习2 |
评测结果 |
AAAAATTTTT |
题目名称 |
排序测试 |
最终得分 |
50 |
用户昵称 |
king'back |
运行时间 |
12.427 s |
代码语言 |
C++ |
内存使用 |
15.57 MiB |
提交时间 |
2016-11-07 19:58:31 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=2000000+1;
int a[maxn],b[maxn];
int n;
void merge(int l,int r);
void mergesort(int l,int mid,int r);
int main()
{
freopen ("sorttest.in","r",stdin);
freopen ("sorttest.out","w",stdout);
cin>>n;
for (int i=1; i<=n; i++)
cin>>a[i];
merge(1,n);
for (int i=1; i<n; i++)
cout<<a[i]<<' ';
cout<<a[n]<<endl;
return 0;
}
void merge(int l,int r)
{
if (l==r) return;
int mid=(l+r)/2;
merge(l,mid);
merge(mid+1,r);
mergesort(l,mid,r);
}
void mergesort(int l,int mid,int r)
{
int i=l,j=mid+1,len=l;
while (i<=mid && j<=r)
{
if (a[i]<a[j])
{
b[len]=a[i];len++;i++;
}
else
{
b[len]=a[j];len++;j++;
}
}
while (i<=mid)
{
b[len]=a[i]; len++; i++;
}
while (j<=r)
{
b[len]=a[j]; len++; j++;
}
for (int k=l; k<=r; k++)
a[k]=b[k];
}