백준 10090 Counting Inversions C++

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

출력

Write the count of inversions on the standard output.

제한

• 2 ≤ n ≤ 100 0000

설명

4 2 7 1 5 6 3

4-2 1 3 → 3

2 - 1          → 1

  7-1 5  6 3  → 4

     1              → 0

        5 -   3    → 1

           6- 3    → 1

                      10개

Inversion ⇒ permutation (bigger one - small one)

브루트 포스 ⇒ O(N^2) 시간제한초과

다른 방식!!

mergesort ⇒ O(NlogN) 시간제한 지킴

따라서 mergesort

왼쪽 오른쪽

merge 시

ㅁㅁㅁㅁ ㅁㅁㅁㅁ

임시배열X 임시배열O

왼쪽배열에 아직 남아있는 원소 > 오른쪽 배열에 있던 원소

  4 2 7 1 5 6 3

  4 2 7 1  /  5 6 3

  4 2 / 7 1 / 5 6 / 3

  2 4 / 17  / 5 6 / 3   → 2

  1 2 4 7  / 3 5 6 → 

풀이

#include <iostream>
using namespace std;

int arr[1000001];
int tmp[1000001];

long long int cnt = 0;

void merge(int start, int mid, int end) {
	int n1, n2;
	n1 = mid - start + 1;
	n2 = end - mid;
	int * left = new int[n1];
	int * right = new int[n2];
	//cout << "beginning" << '\n';
	//cout << "start: " << start << '\n';
	//cout << "mid: " << mid << '\n';
	//cout << "end: " << end << '\n';
	//cout << "n1: " << n1 << '\n';
	//cout << "n2: " << n2 << '\n';
	
	//left array and right array
	
	for (int i = 0; i < n1; i++) {
		left[i] = arr[start + i];
		//cout << "left[" << i << "]: " << left[i] << '\n';
	}

	for (int i = 0; i < n2; i++) {
		right[i] = arr[mid + 1 + i];
		//cout << "right[" << i << "]: " << right[i] << '\n';
	}
	//cout << "start merge sort" << '\n';
	//merge array and count inversion
	int left_index = 0, right_index = 0, arr_index = start;

	
	while ((left_index < n1) && (right_index < n2)) {
		//cout << "left[" << left_index << "]: " << left[left_index] << '\n';
		//cout << "right[" << right_index << "]: " << right[right_index] << '\n';

		if (left[left_index] <= right[right_index]) {
			arr[arr_index] = left[left_index];
			left_index++;
		}

		else {
			cnt += n1 - left_index;
			arr[arr_index] = right[right_index];
			right_index++;			
			//cout << "cnt: "<< cnt << '\n';
		}
		
		arr_index++;
	}

	//copy remaining element
	while (left_index < n1) {
		arr[arr_index] = left[left_index];
		left_index++;

		arr_index++;
	}

	while (right_index < n2) {
		arr[arr_index] = right[right_index];
		right_index++;

		arr_index++;
	}
	//for (int i = start; i <= end; i++) {
		//cout << "arr[" << i << "]: " << arr[i] << '\n';
	//}
	
	//cout << "end" << '\n' << '\n';
}

void mergesort(int start, int end) {
	if (start < end) {
		int mid = start + (end - start) / 2;

		mergesort(start, mid);
		mergesort(mid + 1, end);
		merge(start, mid, end);
	}
}
int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	mergesort(0, n - 1);
	
	cout << cnt;

	return 0;
}