2299.cpp

这些是我到目前在PKU上做出的题目

#include <iostream>
using namespace std;
#define MAX_NUM 1000000000
#define MAX_SIZE 500001
__int64 sum=0;

void merge(int *pa,int p,int q,int r)
{
    int n1,n2,i,j,k;
    n1=q-p+1;
    n2=r-q;
    int *p1,*p2;
    p1=new int[n1+1];
    p2=new int[n2+1];
    for(i=0;i<n1;i++)
        *(p1+i)=*(pa+p+i);
    for(i=0;i<r-q;i++)
        *(p2+i)=*(pa+q+i+1);
    *(p1+n1)=MAX_NUM;
    *(p2+n2)=MAX_NUM;
    i=0;j=0;
    for(k=p;k<=r;k++)
    {
        if(*(p1+i)>=*(p2+j))
        {
            *(pa+k)=*(p2+j);
            j++;
            sum+=(q+1-(i+p));
        }
        else
        {
            *(pa+k)=*(p1+i);
            i++;
        }
    }
    free(p1);
    free(p2);
}
void merge_sort(int *pa,int p,int r)
{
    if(p<r)
    {
        int q=(p+r)/2;
        merge_sort(pa,p,q);
        merge_sort(pa,q+1,r);
        merge(pa,p,q,r);
    }
}

int main()
{
    static int A[MAX_SIZE];
    int i,n;
    while(scanf("%d",&n),n!=0)
    {
        for(i=0;i<n;i++)
            scanf("%d",&A[i]);
        int *pa=A;
        merge_sort(pa,0,n-1);
        printf("%I64d\n",sum);
        sum=0;
    }   
    return 0;
}