13884번: DA-Sort

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

$O(pn\lg n)$

주어진 수열을 {ai}, 정렬한 수열을 {bi}라 하자.
연속한 b1...bj 각각과 같은 ai들의 인덱스 i가 증가하도록 최대 j를 잡자.
그러면 bj+1...bn 들은 삭삽 과정을 한번씩은 수행해야 한다. 답은 n-j

#include<cstdio>
#include<algorithm>
using namespace std;
int p, k, n, a[1000], b[1000];
int main() {
    scanf("%d", &p);
    while (p--) {
        scanf("%d%d", &k, &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            b[i] = a[i];
        }
        sort(b, b + n);
        int h = 0;
        for (int i = 0; i < n; i++) if (a[i] == b[h]) h++;
        printf("%d %d\n", k, n - h);
    }
    return 0;
}