SPOJ.COM - Thuật toán bài BOOKS1 - Copying Books

Posted on September 25th, 2016

Đề 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

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

(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 mình 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 mình 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 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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!