Chặt nhị phân kết quả phân bổ gói tài nguyên
Trung tâm siêu máy tính AI Empire Academy có N gói tác vụ huấn luyện mô hình ngôn ngữ xếp thành một hàng dài, gói thứ i có khối lượng tính toán là Ai (1 ≤ N ≤ 105, 1 ≤ Ai…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: binary search, loops, functions.
Nội dung đề bài
Mục tiêu kiến thức
- Áp dụng kỹ thuật Chặt nhị phân trên không gian kết quả (Binary Search on Answer).
- Xây dựng hàm kiểm tra tính khả thi
check(mid)bằng thuật toán Tham lam (Greedy) trong thời gian O(N). - Nhận diện tính đơn điệu của hàm mục tiêu (Monotonicity property).
- Đạt độ phức tạp tối ưu O(N log(∑ A)).
Mô tả bài toán
Trung tâm siêu máy tính AI Empire Academy có N gói tác vụ huấn luyện mô hình ngôn ngữ xếp thành một hàng dài, gói thứ i có khối lượng tính toán là Ai (1 ≤ N ≤ 105, 1 ≤ Ai ≤ 109).
Có M máy chủ xử lý song song (1 ≤ M ≤ N). Do tính chất phụ thuộc tuần tự của pipeline dữ liệu, các gói tác vụ phải được phân bổ thành M đoạn liên tiếp (mỗi máy chủ nhận một đoạn các gói tác vụ liên tiếp, không máy nào bị bỏ trống và không chia nhỏ một gói tác vụ).
Mục tiêu là tìm cách phân chia sao cho: Khối lượng tính toán lớn nhất mà một máy chủ phải gánh là nhỏ nhất có thể.
Hãy in ra giá trị khối lượng tính toán lớn nhất tối thiểu đó.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N và M (1 ≤ M ≤ N ≤ 105).
- Dòng 2: Gồm N số nguyên dương A1, A2, …, AN (1 ≤ Ai ≤ 109).
Output
In ra một số nguyên duy nhất là giá trị khối lượng tính toán lớn nhất nhỏ nhất có thể.
Ràng buộc
- 1 ≤ M ≤ N ≤ 105.
- 1 ≤ Ai ≤ 109.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
5 3
2 4 7 3 5Output
8Giải thích
Ta có thể chia 5 gói thành 3 phần:
- Máy 1: [2, 4] có tổng = 6.
- Máy 2: [7] có tổng = 7.
- Máy 3: [3, 5] có tổng = 8.
Khối lượng lớn nhất là max(6, 7, 8) = 8. Không thể chia sao cho tải trọng cực đại nhỏ hơn 8 (ví dụ nếu đặt ngưỡng là 7 thì gói có giá trị 7 phải đứng một mình, các phần còn lại không thể chia đủ thành 3 máy hợp lệ).
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.