归并排序 poj2299

归并排序 poj2299

这是题目

把数组分成若干个子序列,再合并

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef  long long ll;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);const int MAXN=500005;
const int MOD=10000000;
const int INF=0x7fffffff;
int n;
int a[MAXN]; int left_t[MAXN],right_t[MAXN];
ll ans = 0;void merge(int a[],int p,int mid,int r){//合并int n1 = mid - p + 1;int n2 = r - mid ,i,j;for(int i=1;i<=n1;i++) left_t[i] = a[p+i-1];for(int i=1;i<=n2;i++) right_t[i] = a[mid+i];left_t[n1+1] = INF;right_t[n2+1] = INF;i=1,j=1;for(int k=p;k<=r;k++){if(left_t[i] <= right_t[j]){a[k] = left_t[i];i++;}else {a[k] = right_t[j];j++;//ans+=n1-i+1;}}
}			  
void MergeSort(int a[],int first,int last){//分组int mid = 0;if(first < last){mid = (first + last) / 2;MergeSort(a,first,mid);MergeSort(a,mid+1,last);merge(a,first,mid,last);}
}int main(){ // 归并排序 SIS;while(cin>>n && n!=0){//ans = 0;for(int i=0;i<n;i++)cin>>a[i];MergeSort(a,0,n-1);cout<< ans <<endl;}return 0;
}