레이팅 미적용베시는 \([1, N]\) 범위의 정수를 입력받아 \([1, N]\) 범위의 정수를 반환하는 특별한 함수 \(f(x)\)를 가지고 있다(\(1 \le N \le 2 \cdot 10^5\)). 함수 \(f(x)\)는 정수 \(N\)개 \(a_1 \ldots a_N\)으로 정의되며, \(f(x) = a_x\)(\(1 \le a_i \le N\))이다.
베시는 이 함수가 멱등이기를 원한다. 즉, 모든 정수 \(x \in [1, N]\)에 대해 \(f(f(x)) = f(x)\)를 만족해야 한다.
베시는 비용 \(c_i\)를 지불하고 \(a_i\)의 값을 \([1, N]\) 범위의 임의의 정수로 바꿀 수 있다(\(1 \le c_i \le 10^9\)). \(f(x)\)를 멱등으로 만들기 위해 베시가 지불해야 하는 총비용의 최솟값을 구하시오.
Problem credits: Avnith Vijayram
배점
서브태스크:
- 입력 3: \(N\le 20\)
- 입력 4-9: \(a_i\ge i\)
- 입력 10-15: 모든 \(a_i\)가 서로 다르다.
- 입력 16-21: 추가 제약이 없다.
추가로, 마지막 세 서브태스크 각각에서 테스트의 앞쪽 절반은 모든 \(i\)에 대해 \(c_i=1\)을 만족한다.
Problem credits: Avnith Vijayram
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 공백으로 구분된 정수 \(N\)개 \(a_1,a_2,\dots,a_N\)이 주어진다.
셋째 줄에 공백으로 구분된 정수 \(N\)개 \(c_1,c_2,\dots,c_N\)이 주어진다.
\(f(x)\)를 멱등으로 만들기 위해 베시가 지불해야 하는 총비용의 최솟값을 출력한다.
5
2 4 4 5 3
1 1 1 1 13We can change \(a_1 = 4\), \(a_4 = 4\), \(a_5 = 4\). Since all \(c_i\) equal one, the
total cost is equal to \(3\), the number of changes. It can be shown that there is
no solution with only \(2\) or fewer changes.
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 97We change \(a_3 = 3\) and \(a_4 = 4\). The total cost is \(2+5=7\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Gold