BOJ1517 - 버블소트 (inversion count)

https://www.acmicpc.net/problem/1517

 

<문제설명>

주어진 숫자배열을 버블소트할 때 swap연산의 회수를 nlogn시간에 구하라

 

<풀이>

https://justicehui.github.io/ps/2019/04/23/BOJ1517/

이분 풀이 참고

 

<코드>

ll n, a[MAX], b[MAX], ans;
void msort(int st, int en) {
	if (st == en) return;

	int mid = (st + en) / 2;
	msort(st, mid);
	msort(mid + 1, en);

	ll i = st, j = mid+1, k = 0, cnt=0;
	while (i <= mid && j <= en) {
		if (a[i] <= a[j]) {
			b[k++] = a[i++];
			ans += cnt;
		}
		else {
			b[k++] = a[j++];
			cnt++;
		}
	}
	while (i <= mid) b[k++] = a[i++], ans += cnt;
	while (j <= en) b[k++] = a[j++];

	for (int i = st; i <= en; i++)
		a[i] = b[i - st];
}

int main() {
	FAST;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	msort(0, n - 1);

	cout << ans << '\n';
}