Hàm Của Bessie

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie định nghĩa hàm $f (x)$ trên tập $[1, N]$ bởi $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ , trong đó $f (x) = a_{x}$ .

Cô muốn biến $f$ thành hàm lũy đẳng (idempotent), nghĩa là $f (f (x)) = f (x)$ với mọi $x \in [1, N]$ .

Để thay đổi $a_{i}$ thành bất kỳ giá trị nào trong $[1, N]$ , cô phải trả chi phí $c_{i}$ . Hãy tìm tổng chi phí nhỏ nhất để đạt được tính lũy đẳng.

Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ )
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq N$ )
Dòng 3: $N$ số nguyên $c_{1}, c_{2}, \dots, c_{N}$ ( $1 \leq c_{i} \leq 10^{9}$ )

In ra tổng chi phí nhỏ nhất.

Input	Output	Giải thích
5 2 4 4 5 3 1 1 1 1 1	3	Đổi $a_{1} = 4$ , $a_{4} = 4$ , $a_{5} = 4$ , tổng chi phí 3.
8 1 2 5 5 3 3 4 4 9 9 2 5 9 9 9 9	7	Đổi $a_{3} = 3$ , $a_{4} = 4$ , tổng chi phí $2 + 5 = 7$ .

Bình luận

Không có bình luận tại thời điểm này.