佳佳的难题.cpp

来自「有关算法设计与分析的几个小程序（查找与替换问题、炒饭问题、寻宝问题等）」· C++ 代码 · 共 46 行

//分治的思想，归并排序去做。
#include<iostream>
using namespace std;
int s[1000002],t[1000002];
__int64 cnt;

void sortf(int b,int e)
{
     if(b >= e )
     return;
     sortf(b,(b+e)/2);//归并排序的递归步
     sortf((b+e)/2+1,e);
//以下是归并排序的合并步。S为原数组，t为存过程值的辅助数组。
     int i = b,j = (b+e)/2+1, k = b;
     while(i<=(b+e)/2&&j<=e)
     {
        if(s[i] <= s[j])
            t[k++] = s[i++];
        else
        {
            cnt += j - k;
            t[k++] = s[j++];
        }
    }
    while(i<=(b+e)/2)t[k++]=s[i++];
    while(j<=e)t[k++]=s[j++];
    for(i=b;i<=e;i++)
    s[i] = t[i];
}

int main()
{
    int i,n;
	scanf("%d",&n);
    while(n!=0)
    {
        for(i=0;i<n;i++)
            scanf("%d",&s[i]);
        cnt = 0;
        sortf(0,n-1);
        printf("%I64d\n",cnt);
		scanf("%d",&n);
    }
    return 0;
}