Olympic Sinh Viên 2024 - Không chuyên - Đăng ký học phần

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 22
    YougiTuber  commented on Dec. 18, 2024, 9:39 a.m.

    Spoil ⚠️

    Tham lam:

    Luôn chọn các phần tử có giá trị ~a_i~ liên tiếp nhau sau khi đã sắp xếp theo ~a_i~

    Cách ~1~: Binary search

    • Chặt nhị phân giá trị ~x~ là max có thể giữa ~2~ số được chọn
    • Duyệt từ ~1~ đến ~n~, nếu hiệu giữa số hiện tại và số trước đó nhỏ hơn hoặc bằng ~x~, thêm giá trị ~b_i~ vào tổng. Ngược lại số ~i~ không thể chọn cùng số ~i-1~ trước đó, reset tổng thành ~b_i~.

    Cách ~2~: DSU

    • Dựng cạnh có trọng số ~a_{i+1} - a_i~ giữa ~i~ và ~i+1~
    • Sắp xếp các cạnh theo trọng số
    • Nối các thành phần liên thông lại đến khi có một thành phần liên thông có tổng lớn hơn hoặc bằng ~C~. Kết quả là trọng số cạnh cuối cùng được thêm vào.