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);
		}

	}

}

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