50分求助!

P1908 逆序对

Zbcxcj @ 2019-05-13 08:15:00

跪求各位大佬帮忙看一下我的代码,始终只有前面一半的用例能过,ans已经设成了long long型了还是没用

#include <bits/stdc++.h>

using namespace std;

// 求数组a(lo..hi)的逆序对个数,逆序对横跨中间索引mid
// 假定a(lo..hi)的两半分别都排好了序(这个方法其实是一个归并排序,temp作为临时数组)
long long merge_pairs(int* a, int* temp, int lo, int mid, int hi) {
    int i = lo;
    int j = mid + 1;
    int k = lo;
    long long cnt = 0;

    while(i <= mid && j <= hi) {
        if(a[i] > a[j]) {
            temp[k++] = a[j++];
            cnt += mid - i + 1;  // 左半边中a[i]与i之后的所有元素与a[j]构成逆序对
        }
        else {
            temp[k++] = a[i++];
        }
    }

    while(i <= mid) temp[k++] = a[i++];
    while(j <= hi)  temp[k++] = a[j++];
    for(int i = lo; i <= hi; i++) {
        a[i] = temp[i];
    }

    return cnt;
}

// 求数组a(lo..hi)的逆序对个数,assert(lo <= hi)
long long reversal_pairs_detail(int* a, int* temp, int lo, int hi) {
    if(lo == hi) return 0;

    long long cnt = 0;
    int mid = (lo + hi) / 2;
    cnt += reversal_pairs_detail(a, temp, lo, mid);
    cnt += reversal_pairs_detail(a, temp, mid+1, hi);
    cnt += merge_pairs(a, temp, lo, mid, hi);
    return cnt;
}

// 求数组a前n个元素中逆序对个数
int reversal_pairs(int* a, int n) {
    if(!n) return 0;
    int temp[n+1];
    return reversal_pairs_detail(a, temp, 0, n-1);
}

// 快读
inline int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x*10 + (ch^48), ch = getchar();
    return x*f;
}

int main() {
    int n; cin >> n;
    int a[n+1];

    for(int i = 0; i < n; i++) {
        a[i] = read();
    }

    cout << reversal_pairs(a, n) << endl;
    return 0;
}

by _xqy_ @ 2019-05-13 11:53:33

直接利用归并排序求逆序对便好了,为什么要加入其他函数???


by Strong_Jelly @ 2019-05-27 21:01:50

全long long


|