poj 2299再帰と分治戦略
4075 ワード
package hard;
import java.io.BufferedInputStream;
import java.util.Scanner;
/**
* poj2299
*
* , !!!
* @author NC
*/
public class Poj2299 {
static long num = 0;// long 。。。。
public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while (scan.hasNext()) {
int n = scan.nextInt();
if (n == 0) {
break;
}
num = 0;
int data[] = new int[n];
for (int i = 0; i < n; i++) {
data[i] = scan.nextInt();
}
mergeSort(data, 0, n - 1);
System.out.println(num);
}
}
static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(array, left, center);
mergeSort(array, center + 1, right);
Merge(array, left, center, right);
}
}
static void Merge(int[] array, int left, int center, int right) {
//[1,2,3,4] left=1,ceter=2,right=4
int[] temp = new int[right - left + 1];//
int i = left;
int j = center + 1;
int k = 0;
while (i <= center && j <= right) {
if (array[i] > array[j]) {
temp[k++] = array[j++];
/* array[i] array[j] */
num += center - i + 1;
} else {
temp[k++] = array[i++];
}
}
while (i <= center) {
temp[k++] = array[i++];
}
while (j <= right) {
temp[k++] = array[j++];
}
// temp[] array[]
for (i = left, k = 0; i <= right; i++, k++) {
array[i] = temp[k];
}
}
}
#include <stdio.h>
#include <stdlib.h>
long long num ;// long long
long data[500000];
long temp[500000];
void Merge(long array[], long left, long center, long right) {
//[1,2,3,4] left=1,ceter=2,right=4
int i = left;
int j = center + 1;
int k = 0;
while (i <= center && j <= right) {
if (array[i] > array[j]) {
temp[k++] = array[j++];
/* array[i] array[j] */
num += center - i + 1;
} else {
temp[k++] = array[i++];
}
}
while (i <= center) {
temp[k++] = array[i++];
}
while (j <= right) {
temp[k++] = array[j++];
}
// temp[] array[]
for (i = left, k = 0; i <= right; i++, k++) {
array[i] = temp[k];
}
}
void mergeSort(long array[], long left, long right) {
if (left < right) {
long center = (left + right) / 2;
mergeSort(array, left, center);
mergeSort(array, center + 1, right);
Merge(array, left, center, right);
}
}
int main() {
long n = 0, i;
while (scanf("%ld", &n)) {
if (n == 0) {
break;
}
for (i = 0; i < n; i++) {
scanf("%ld", &data[i]);
}
mergeSort(data,0, n-1);
printf("%lld
", num);
num = 0;
}
return 1;
}