> 
> import java.math.BigInteger;
> import java.util.Scanner;
> 
> public class Main {
> 
> 	private static BigInteger sum = BigInteger.valueOf(0);
> 
> 	private static void merge(int[] a, int s, int m, int t) {
> 		long[] tmp = new long[t - s + 1];
> 
> 		int i = s, j = m, k = 0;
> 		while (i < m && j <= t) {
> 			if (a[i] <= a[j]) {
> 				tmp[k] = a[i];
> 				k++;
> 				i++;
> 			} else {
> 				tmp[k] = a[j];
> 				// sum += (j - i) - (j - m);
> 				sum = sum.add(BigInteger.valueOf((j - i) - (j - m)));
> 				j++;
> 				k++;
> 			}
> 		}
> 		while (i < m) {
> 			tmp[k] = a[i];
> 			i++;
> 			k++;
> 		}
> 
> 		while (j <= t) {
> 			tmp[k] = a[j];
> 			j++;
> 			k++;
> 		}
> 
> 		System.arraycopy(tmp, 0, a, s, tmp.length);
> 
> 		tmp = null;
> 	}
> 
> 	public static void mergeSort(int[] a, int s, int len) {
> 
> 		while (len <= (a.length >> 1)) {
> 			int size = a.length;
> 			int mid = size / (len << 1);
> 			int c = size & (len - 1);
> 
> 			// -------归并到只剩一个有序集合的时候结束算法-------//
> 			// if (mid == 0)
> 			// return;
> 
> 			// ------进行一趟归并排序-------//
> 			for (int i = 0; i < mid; ++i) {
> 				s = i * len << 1;
> 				merge(a, s, s + len, (len << 1) + s - 1);
> 			}
> 
> 			// -------将剩下的数和倒数一个有序集合归并-------//
> 			if (c != 0)
> 				merge(a, size - c - (len >> 1), size - c, size - 1);
> 			//
> 			// for (int i = 0; i < a.length; ++i) {
> 			// System.out.print(a[i] + " ");
> 			// }
> 			// System.out.println();
> 
> 			// -------递归执行下一趟归并排序------//
> 			len <<= 1;
> 		}
> 		// mergeSort(a, 0, 2 * len);
> 	}
> 
> 	public static void main(String[] args) {
> 
> 		Scanner sc = new Scanner(System.in);
> 
> 		while (true) {
> 			sum = BigInteger.valueOf(0);
> 			int size = sc.nextInt();
> 			if (size == 0)
> 				break;
> 			int[] a = new int[size];
> 			for (int i = 0; i < size; ++i) {
> 				a[i] = sc.nextInt();
> 			}
> 			mergeSort(a, 0, 1);
> 			System.out.println(sum);
> 		}
> 
> 	}
> 
> }
我的邮箱：lazy_p@163.com

• Re:re n次快疯了，求牛人解答why？ (1766) wskwsk 2010-04-22 18:29:21