[백준 1377] 버블 소트

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

1377번: 버블 소트

요구사항

몇번의 이동을 해야지 정렬이 되는가

 

풀이

버블 소트로 풀게 되면 n*n 이므로 통과가 안된다

원래의 인덱스가 몇번 이동했느냐로 풀이해야한다

 

1. 정렬(stable)

2. 인데스가 몇번 이동했는지 확인

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
int n;
priority_queue<ll, vector<ll>, greater<ll>> q;
struct go {
	int x;
	int y;
};
go a[1000005];
go buf[1000005];
//1000000
void mer(go arr[], int len) {
	//cout << "A" << endl;
	if (len < 2) return;
	int i, j, mid, k;
	i = 0;
	mid = len / 2;
	k = 0;
	j = mid;
	mer(arr, mid);
	mer(arr + mid, len - mid);
	while (i < mid && j < len) {
	//	cout << "A" << endl;
		if (arr[i].x < arr[j].x)
			buf[k++] = arr[i++];
		else if (arr[i].x == arr[j].x) {
			if (arr[i].y > arr[j].y)
				buf[k++] = arr[j++];
			else
				buf[k++] = arr[i++];
		}
		else {
			buf[k++] = arr[j++];
		}
	}
	while (i < mid) {
	//	cout << "B" << endl;
		buf[k++] = arr[i++];
	}
	while (j<len) {
	//	cout << "C" << endl;
		buf[k++] = arr[j++];
	}
	for (int i = 0; i < len; i++) {
		arr[i] = buf[i];
	}
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		a[i].x = x;
		a[i].y = i;
		
	}
	mer(a, n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (ans < a[i].y - i) {
			ans = a[i].y - i;
		}
	}
	printf("%d", ans + 1);
}