R
rabbit.thuy
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Mọi người giúp mình bài này
Văn bản là một dãy gồm N từđánh số từ 1 đến N. Từ thứ i có độ dài là wi (i=1, 2,... N). Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng cóđộ dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L.Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số (L-S), trong đóS là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.Tìm cách phân trang với hệ số phạt nhỏ nhất.
Input
Dòng 1 chứa 2 số nguyên dương N, L (N<=6000,L<=1000)
Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N
Output
In ra hệ số phạt nhỏ nhất
Ví dụ
Input:
4 5
3
2
2
4
Output:
2
Link: http://vn.spoj.pl/problems/PTRANG/
Văn bản là một dãy gồm N từđánh số từ 1 đến N. Từ thứ i có độ dài là wi (i=1, 2,... N). Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng cóđộ dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L.Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số (L-S), trong đóS là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.Tìm cách phân trang với hệ số phạt nhỏ nhất.
Input
Dòng 1 chứa 2 số nguyên dương N, L (N<=6000,L<=1000)
Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N
Output
In ra hệ số phạt nhỏ nhất
Ví dụ
Input:
4 5
3
2
2
4
Output:
2
Link: http://vn.spoj.pl/problems/PTRANG/