比赛 |
noip2016普及练习2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
排序测试 |
最终得分 |
100 |
用户昵称 |
Furyton |
运行时间 |
9.817 s |
代码语言 |
C++ |
内存使用 |
15.57 MiB |
提交时间 |
2016-11-07 21:18:56 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2000000+10;
int n,ans;
int a[maxn],b[maxn];
void merge(int,int,int);
int main()
{
freopen("sorttest.in","r",stdin);
freopen("sorttest.out","w",stdout);
scanf("%d",&n);
for(int i=0; i!=n; ++i)
{
scanf("%d",&a[i]);
}
merge(0,(n-1)/2,n-1);
for(int i=0; i!=n; ++i)
printf("%d ",b[i]);
return 0;
}
void merge(int l,int mid,int r)
{
if(l==r)return;
merge(l,(l+mid)/2,mid);
merge(mid+1,(mid+1+r)/2,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r)
{
if(a[i]<=a[j])
{
b[k]=a[i];i++;
ans+=j-(mid+1);
}
else
{
b[k]=a[j];j++;
}
k++;
}
while(i<=mid)
{
b[k]=a[i];i++;k++;
ans+=r-mid;
}
while(j<=r)
{
b[k]=a[j];j++;k++;
}
for(int i=l; i<=r; i++)
a[i]=b[i];
}