SPOJ.COM – Thuật toán bài BOOKS1 – Copying Books
Đề bài:
Trước khi máy photo sách được phát minh ra, việc tạo ra một bản photo cho một quyển sách là vô cùng khó khăn. Tất cả nội dung phải được ghi chép lại bằng tay. Một người thợ được đưa cho quyển sách và anh ta phải hoàn thành nó sau một vài tháng. Một trong những người thợ nổi tiếng sống ở thế kỉ 15, và tên anh ta là Tèo. Nhưng dù sao thì công việc cũng vô cùng chán và buồn tẻ. Và chỉ có một cách để cải thiện tình hình đó là thuê những người thợ khác.
Hồi đó, có một đoàn múa hát muốn trình diễn một vở kịch rất nổi tiếng. Kịch bản được chia ra làm nhiều cuốn. Và diễn viên cần có nhiều bản copy của chúng. Tưởng tượng rằng bạn có m cuốn sách (đánh số từ 1, 2,…, m) có số trang lần lượt là p[1], p[2], …, p[m]. Và bạn phải tạo ra bản copy của mỗi cuốn đó. Nhiệm vụ của bạn là chia m cuốn sách đó cho k người thợ, k <= m. Mỗi cuốn chỉ phép giao cho một người thợ duy nhất. Và mỗi người thợ phải nhận những cuốn sách liên tiếp nhau. Có nghĩa là tồn tại một dãy số tăng dần thoả mãn 0 = b[0] < b[1] < b[2] < … < b[k] = m sao cho người thợ thứ i lấy những cuốn sách được đánh số giữa b[i-1] + 1 và b[i]. Thời gian để tạo ra bản copy của tất cả những cuốn sách được xác định dựa trên người thợ nhận nhiều việc nhất. Vì vậy, nhiệm vụ đặt ra là tối thiểu hoá số lượng trang sách lớn nhất được giao cho mỗi người thợ. Hãy tìm ra giải pháp cho vấn đề này.
Đầu vào:
Đầu vào gồm N trường hợp (N <= 200). Bắt đầu là số nguyên dương N, là số lượng trường hợp. Sau đó là các trường hợp. Mỗi cái gồm chính xác 2 dòng. Dòng đầu tiên gồm 2 số nguyên m và k, 1 <= k <= m <= 500. Dòng thứ hai bao gồm các số p1, p2,…, pm phân cách nhau bởi dấu cách. Tất cả giá trị này đều là số dương và nhỏ hơn 10000000.
Đầu ra:
Với mỗi trường hợp, in ra trên một dòng , bao gồm dãy p1, p2,…, pm được chia làm k phần. Sao cho tổng lớn nhất của mỗi phần là nhỏ nhất. Và ưu tiên cho những người thợ đầu tiên trước – nghĩa là người thợ đầu tiên làm ít hơn người thợ thứ 2, … Sử dụng dấu ‘/’ để phân cách các phần. Có 1 dấu cách duy nhất giữa 2 số liên tiếp; giữa số và ‘/’.
Ví dụ:
Đầu vào:
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
Đầu ra:
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
Giải thích:
-
Trường hợp thứ nhất, tổng lớn nhất của mỗi phần là 1700
-
Trường hợp thứ hai, tổng lớn nhất mỗi phần là 200
Các bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/BOOKS1/
Phân tích:
- Với bài toán số lượng đầu vào khá lớn như này, ta sẽ không thể sử dụng thuật toán vét cạn - Brute force + Ở đây ta sẽ dùng thuật toán chia để trị - Divide and Conquer.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
#include<iostream> | |
using namespace std; | |
typedef long long int ll; | |
const int MAX = 505; | |
ll M, K; // Lưu số lượng cuốn sách, và số phần cần chia | |
ll Left,Right, mid; | |
ll Page[MAX]; // Lưu số lượng trang sách của mỗi cuốn | |
ll Index[MAX]; // Mảng lưu chỉ số của phần tử đầu tiên của mỗi phần | |
ll ValidIndex[MAX]; // Kết quả cuối cùng | |
// Cập nhật lại từng phần sao cho tổng mỗi phần không lớn hơn mid | |
void Update(ll id) | |
{ | |
ll sum = 0, t = Index[id]; | |
for(ll i = Index[id + 1] - 1; i >= t; i--) | |
{ | |
sum += Page[i]; | |
if(sum == mid) | |
{ | |
Index[id] = i; | |
break; | |
}else if(sum > mid) | |
{ | |
Index[id] = i + 1; | |
break; | |
} | |
} | |
} | |
// Kiểm tra xem với với số lượng lớn nhất của các phần là mid | |
// có hợp lệ hay không | |
bool IsValid() | |
{ | |
for(int i = 0; i < K; i++) | |
Index[i] = i; | |
Index[K] = M; | |
// Cập nhật lại từng phần | |
for(int i = K - 1; i >= 0; i--) | |
Update(i); | |
// Nếu sau | |
if (Index[0] > 0) return false; | |
return true; | |
} | |
int main() | |
{ | |
ios_base::sync_with_stdio(false); | |
// comment dòng này trước khi submit | |
freopen("input.txt","r",stdin); | |
int T; | |
cin >> T; | |
for(int tc = 0; tc < T; tc++) | |
{ | |
ll max_page = 0; // Tìm ra cuốn sách có nhiều trang nhất | |
ll sum_page = 0; // Tìm tổng số trang | |
cin >> M >> K; | |
for(int i = 0; i < M; i++) | |
{ | |
cin >> Page[i]; | |
if(Page[i] > max_page) max_page = Page[i]; | |
sum_page += Page[i]; | |
} | |
// Khi chia ra thành các phần, thì tổng lớn nhất của các phần | |
// sẽ nằm trong khoảng từ Left = max_page (số trang nhiều nhất) | |
// và Right = sum_page (số trang nhiều nhất) | |
Left = max_page; | |
Right = sum_page; | |
// Triển khai thuật toán chia để trị | |
while (Left < Right) | |
{ | |
mid = (Left + Right) / 2; | |
if (IsValid()) | |
{ | |
Right = mid; | |
// Ta dùng mảng để lưu lại chỉ số của các phần tử | |
// để phân chia các phần. | |
for(int i = 0; i < K; i++) | |
ValidIndex[i] = Index[i]; | |
} | |
else | |
{ | |
Left = mid + 1; | |
} | |
} | |
// In ra kết quả | |
for(int i = 0; i < K - 1; i++) | |
{ | |
for(int j = ValidIndex[i]; j < ValidIndex[i+1]; j++) | |
cout << Page[j] << " "; | |
cout << "/ "; | |
} | |
for(int i = ValidIndex[K-1]; i < M; i++) | |
{ | |
cout << Page[i]; | |
if(i == M-1) break; | |
cout << " "; | |
} | |
cout << endl; | |
} | |
return 0; | |
} |
Code by Phạm Văn Lâm