| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 50517 | Accepted: 18534 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence Input
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
题解：归并排序注意对dt主数组的更改，由于数据太大999999999所以要离散化
归并：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
typedef long long LL;
#define mem(x,y) memset(x,y,sizeof(x))
#define T_T while(T--)
#define F(i,x) for(i=1;i<=x;i++)
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
const int MAXN=500010;
int dt[MAXN],b[MAXN];
LL ans;
void mergesort(int l,int mid,int r){
int ll=l,rr=mid+1,pos=l;
while(ll<=mid&&rr<=r){
if(dt[ll]<=dt[rr])b[pos++]=dt[ll++];
else{
ans+=rr-pos;
b[pos++]=dt[rr++];
}
}
for(int i=ll;i<=mid;i++)b[pos++]=dt[i];
for(int i=rr;i<=r;i++)b[pos++]=dt[i];
for(int i=l;i<=r;i++)dt[i]=b[i];
}
void ms(int l,int r){
if(l<r){
int mid=(l+r)>>1;
ms(l,mid);
ms(mid+1,r);
mergesort(l,mid,r);
}
}
int main(){
int N;
while(~scanf("%d",&N),N){
int i,j;
ans=0;
F(i,N)
SI(dt[i]);
ms(1,N);
PL(ans);puts("");
}
return 0;
}
原文：http://www.cnblogs.com/handsomecui/p/5002137.html