【题解】POJ P2299 【Ultra-QuickSort】

这里也是跑一个归并排序就好了,水题一道。
注意$cnt$每次清$0$就好了

#include<cstdio>

typedef long long int64;

const int64 MAXN = 666666;
int64 a[MAXN],b[MAXN],cnt = 0;

void merge(int l,int mid,int r){
    int i = l,j = mid + 1;
    for(int k = l;k <= r;k++){
        if(j > r || i <= mid && a[i] <= a[j]){
            b[k] = a[i++];
        }else{
            b[k] = a[j++];
            cnt += mid - i + 1;
        }
    }
    for(int k = l;k <= r;k++){
        a[k] = b[k];
    }
}

void mergeSort(int l,int r){
    int mid = (l + r) >> 1;
    if(l != r){
        mergeSort(l,mid);
        mergeSort(mid + 1,r);
        merge(l,mid,r);
    }
}

int main(){
    int64 n;
    while(scanf("%lld",&n) == 1 && n){
        for(int i = 0;i < n;i++){
            scanf("%lld",&a[i]);
        }

        mergeSort(0,n - 1);

        printf("%lld\n",cnt);
        cnt = 0;
    }
    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注