> 请问大家如何应对这种问题呢？
> 
> #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. (95) sleepingpig 2009-08-09 00:25:19