1838번: 버블 정렬

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

$O(n\lg n)$

답은 각 수에 대해 정렬 후 앞으로 가게 되는 칸 수의 최댓값

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[500000];
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i].first), p[i].second = i;
    sort(p, p + n);
    for (int i = 0; i < n; i++) r = max(r, p[i].second - i);
    printf("%d", r);
    return 0;
}