레이팅 미적용이제는 익숙한 일이 된 듯, 농부 존은 사진 촬영을 위해 \(1\ldots N\)으로 편리하게 번호가 붙은 \(N\) (\(1\le N\le 10^5\))마리의 소들을 일렬로 세우고 있다.
처음에 소들은 왼쪽에서 오른쪽으로 \(a_1,a_2,\ldots,a_N\) 순서로 서 있다. 농부 존의 목표는 소들을 왼쪽에서 오른쪽으로 \(b_1,\ldots,b_N\) 순서로 세우는 것이다. 이를 위해 그는 순서에 대한 일련의 수정을 수행할 수 있다. 각 수정은 소 한 마리를 골라 왼쪽으로 몇 칸 옮기는 것으로 이루어진다.
농부 존이 소들을 원하는 순서로 세우기 위해 필요한 최소 수정 횟수를 구하시오.
출제자: Benjamin Qi
배점
- 테스트 케이스 3-6은 \(N\le 100\)을 만족한다.
- 테스트 케이스 7-10은 \(N\le 5000\)을 만족한다.
- 테스트 케이스 11-14에는 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다. 둘째 줄에 \(a_1,a_2,\ldots,a_N\)이 주어진다. 셋째 줄에 \(b_1,b_2,\ldots,b_N\)이 주어진다.
농부 존이 원하는 순서를 만들기 위해 필요한 최소 수정 횟수를 출력한다.
5
1 2 3 4 5
1 2 3 4 50In this example, the cows are already in the desired order, so no modifications are required.
5
5 1 3 2 4
4 5 2 1 32In this example, two modifications suffice. Here is one way Farmer John can rearrange his cows:
- Choose cow \(4\) and move it four positions to the left.
- Choose cow \(2\) and move it two positions to the left.
5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Bronze