Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Sức chứa nhỏ nhất giao hàng

    Một băng chuyền cảng cần chuyển nnn kiện hàng có khối lượng w1,w2,…,wnw_1, w_2, \dots, w_nw1​,w2​,…,wn​ trong vòng DDD ngày. Mỗi ngày, một con tàu có sức chứa cố định CCC sẽ chở các kiện theo đúng thứ tự đã cho, sao cho tổng khối lượng các kiện chở trong ngày không vượt quá CCC.

    Hãy tìm sức chứa CCC nhỏ nhất sao cho có thể chuyển hết toàn bộ kiện hàng trong tối đa DDD ngày.

    Yêu cầu: dùng tìm kiếm nhị phân trên đáp án (một dạng chia để trị) — nhị phân giá trị CCC, với mỗi CCC kiểm tra (tham lam) số ngày cần dùng — để giải trong O(nlog⁡(∑wi))O(n \log(\sum w_i))O(nlog(∑wi​)).

    Ví dụ: w=[1,2,3,4,5,6,7,8,9,10]w = [1,2,3,4,5,6,7,8,9,10]w=[1,2,3,4,5,6,7,8,9,10], D=5D = 5D=5, sức chứa nhỏ nhất là 151515.

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên nnn và DDD cách nhau bởi dấu cách. Dòng thứ hai chứa nnn số nguyên dương w1,…,wnw_1, \dots, w_nw1​,…,wn​ — khối lượng các kiện, cách nhau bởi dấu cách.

    • Ràng buộc đầu vào:

      1≤D≤n≤1051 \le D \le n \le 10^51≤D≤n≤105, 1≤wi≤1041 \le w_i \le 10^41≤wi​≤104.

    • Định dạng đầu ra:

      In ra một số nguyên là sức chứa nhỏ nhất để chuyển hết hàng trong tối đa DDD ngày.

    Ví dụ:

    Đầu vào:

    10 5
1 2 3 4 5 6 7 8 9 10

    Đầu ra:

    15

    Giải thích:

    Với sức chứa 15 có thể chia thành 5 ngày: (1..5),(6,7),(8),(9),(10).

    Đang tải editor...