记录编号	548543	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.259 s
提交时间	2020-01-23 14:33:09	内存使用	14.04 MiB

#include <iostream>
#include <cstdio>

using namespace std;

int iSort[50000],iTplt[50000];
int iCount = 0;

bool OpenFile()
{
    FILE * fin = freopen("px.in","r",stdin);
    FILE * fout = freopen("px.out","w",stdout);
    if(fin != NULL && fout != NULL)
        return true;
    else
        return false;
}

void Msort(int f,int b)
{
    if(f == b)
        return;
    int mid = (f + b) / 2;
    Msort(f,mid);
    Msort(mid + 1,b);
    int i = f,j = mid + 1,k = f;
    while(i <= mid && j <= b)
    {
        if(iSort[i] <= iSort[j])
        {
            iTplt[k] = iSort[i];
            k++;
            i++;
        }
        else
        {
            iTplt[k] = iSort[j];
            k++;
            j++;
            iCount += mid - i + 1;
        }
    }
    while(i <= mid)
    {
        iTplt[k] = iSort[i];
        k++;
        i++;
    }
    while(j <= b)
    {
        iTplt[k] = iSort[j];
        k++;
        j++;
    }
    for(int i = f;i <= b;i++)
    {
        iSort[i] = iTplt[i];
    }
}

int main()
{
    if(!OpenFile())
        return 0;
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> iSort[i];
    }
    Msort(0,n - 1);
    cout << iCount;
    return 0;
}