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

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 22
    YougiTuber  đã bình luận lúc 18, Tháng 12, 2024, 9:39

    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.