알고리즘/백준 & swacademy
BOJ1517 - 버블소트 (inversion count)
sun__
2020. 2. 20. 11:37
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';
}