티스토리 뷰

문제: icpc.me/2872


책의 순서가 주어졌을 때 책을 정렬하는데 필요한 최소 이동횟수를 출력하는 문제이다.


책을 이동하는 조건은 무조건 하나의 책을 들어서 맨위에 쌓는 방법밖에 없기 때문에


가장 뒤에 있어야 하는 책은 옮길 필요가 없다.


가장 큰 숫자부터 연속 된 숫자가 얼마나 긴 부분 증가 수열을 이루고 있는지 확인하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[300030], here;
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++)
        scanf("%d"&a[i]);
    here = n;
    for (int i = n - 1; i >= 0; i--
        if (a[i] == here)here--;
    printf("%d\n", here);
    return 0;
}
cs


댓글
댓글쓰기 폼