请问大家如何应对这种问题呢？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long LL;
LL swap_cnt;
int backup[500002];
int vec[500002];
void
sub_merge2(int s, int m, int e)//从后向前的合并超时
{
    int i = m, j = e, k = e;
    while (i >= s && j >= (m + 1)) {
        if (vec[i] > vec[j]) {
            swap_cnt += j - m;
            backup[k--] = vec[i--];
        } else {
            backup[k--] = vec[j--];
        }
    }
    while (i >= 0)
        backup[k--] = vec[i--];
    while (j >= (m + 1))
        backup[k--] = vec[j--];
    memcpy(vec + s, backup + s, sizeof(*backup) * (e - s + 1));
}

void
sub_merge(int s, int m, int e) //从前向后合并，400MS
{
    int i = s, j = m + 1, k = s;
    while (i <= m && j <= e) {
        if (vec[i] > vec[j]) {
            swap_cnt += m - i + 1;
            backup[k++] = vec[j++];
        } else {
            backup[k++] = vec[i++];
        }
    }
    while (i <= m)
        backup[k++] = vec[i++];
    while (j <= e)
        backup[k++] = vec[j++];
    memcpy(vec + s, backup + s, sizeof(*backup) * (e - s + 1));
}

void
merge(int s, int e)
{
    if (s >= e)
        return;
    int m = (s + e) / 2;
    merge(s, m);
    merge(m + 1, e);
    sub_merge2(s, m, e);
    return;
}

int
main()
{
    long i, n;
    while (scanf("%ld", &n) == 1 && n != 0) {
        for (i = 0; i < n; i++)
            scanf("%ld", &(vec[i]));
        swap_cnt = 0;
        merge(0, n - 1);
        printf("%lld\n", swap_cnt);
    }
    return 0;
}

• Re:不同的归并求逆序,一个超时一个400MS. (1688) sleepingpig 2009-08-09 00:23:53
  • Re:不同的归并求逆序,一个超时一个400MS. (95) sleepingpig 2009-08-09 00:25:19