SPOJ.COM - Thuật toán bài AE1B - Tables

Posted on September 25th, 2016

Đề bài:

Thuận làm việc như một thợ mộc. Anh đấy đã nhận một hợp đồng để làm s cái bàn bằng gỗ thông. Mặc dù, Thuận có rất nhiều gỗ, nhưng anh ta lại bị hết sạch đinh. Vì vậy, anh ấy cần đi đến cửa hàng và mang về một vài hộp đinh. Hỏi số lượng hộp đinh tối thiểu mà Thuận cần mang về để có đủ đinh cho những chiếc bàn?

Đầu vào

Dòng đầu tiên của đầu vào bao gồm 3 số nguyên n, k và s (1 <= n, k, s <= 1000) phân cách nhau bởi 1 dấu cách. Chúng biểu diễn cho số lượng hộp đinh ở của hàng của Thuận, số lượng đinh cần để làm ra 1 cái bàn và số lượng bàn cần phải làm. Dòng thứ hai bao gồm n (có thể giống nhau) số nguyên ai (1 <= ai <= 1000) phân cách nhau bởi 1 dấu cách, trong đó ai là số lượng đinh ở hộp đinh thứ i tại của hàng.

Đầu ra

Một dòng duy nhất chứa 1 số nguyên - là số lượng hộp đinh tối thiểu mà Thuận cần phải mang về từ cửa hàng để làm s cái bàn. Giả sử là Thuận có đủ số lượng đinh để làm tất cả bàn.

Ví dụ

Đầu vào:

5 6 3 
3 9 5 7 3

Đầu ra:

3

Giải thích:

Để làm 3 cái bàn, mỗi cái cần 6 đinh, tức là cần tổng là 18 cái đinh. Do đó, Thuận cần mang ít nhất là 3 cái hộp từ cửa hàng về nhà. Đáp án có thể là 3 hộp với số lượng đinh lần lượt làm (3, 7, 9) hoặc (9, 5, 7).

Tác giả: Jakub Lacki.

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/AE1B/

Phân tích

Đối với bài toán này, bạn chỉ cần suy nghĩ một cách đơn giản. Đó là mình sẽ bắt đầu chọn từ hộp đinh có số lượng đinh nhiều nhất trước. Cho đến khi đủ số lượng đinh thì khi đó, số lượng hộp đinh cần chọn sẽ là ít nhất. Có hai cách để triển khai:

  • C1: Để có thể chọn được hộp đinh nhiều đinh nhất trước, thì ta có thể sử dụng 1 vòng lặp for để tìm ra phần tử lớn nhất mà chưa được chọn, sau đó đánh dấu nó là đã chọn. Sau khi chọn được hộp nhiều đinh nhất thì ta sẽ kiểm tra xem đã đủ lượng đinh chưa. Khi đủ rồi thì dừng lại.

  • C2: Hoặc cách thứ hai là chúng ta sẽ sắp xếp các hộp đinh theo thứ tự giảm dần số lượng đinh. Sau đó, chỉ cần dùng vòng lặp for để duyệt từ đầu mảng, thì đảm bảo chọn được hộp đinh nhiều nhất trước.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán 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++

Cách 1:

#include<iostream>
using namespace std;

const int MAX = 1000;

int  N;             // Lưu số lượng hộp đinh
int  K;             // Lưu số lượng đinh cần cho 1 cái bàn
int  S;             // Số lượng bàn cần làm
int  Screw[MAX];    // Lưu số lượng đinh của các hộp
bool Mark[MAX];     // Đánh dấu hộp đinh đã được chọn

int FindMax()
{
    int idmax = 0, max = 0;

    for(int i = 0; i < N; i++)
        if(Mark[i] == false && Screw[i] > max)
        {
            max   = Screw[i];
            idmax = i;
        }

    return idmax;
}

int main()
{
    ios::sync_with_stdio(false);

    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    cin >> N >> K >> S;
    for(int i = 0; i < N; i++)
    {
        cin >> Screw[i];
        Mark[i] = false;
    }

    int sum = 0;    // số lượng đinh đã chọn
    int num = 0;    // số lượng hộp đinh đã chọn

    // Số lượng đinh cần thiết cho S cái bàn
    int need = K * S;

    while(sum < need)
    {
        int idmax = FindMax();
        Mark[idmax] = true;
        sum += Screw[idmax];
        num++;
    }

    cout << num << endl;

    return 0;
}

Cách 2:

#include<iostream>
using namespace std;

const int MAX = 1000;

int N;          // Lưu số lượng hộp đinh
int K;          // Lưu số lượng đinh cần cho 1 cái bàn
int S;          // Số lượng bàn cần làm
int Screw[MAX]; // Lưu số lượng đinh của các hộp

void Merge(int *a, int left, int m, int right)
{
    int l = left, r = m+1, k = 0;
    int *temp = new int[right - left + 1];

    while(l <= m && r <= right)
    {
        if(a[l] > a[r]) temp[k++] = a[l++];
        else temp[k++] = a[r++];
    }

    while(l <= m) temp[k++] = a[l++];

    while(r <= right) temp[k++] = a[r++];

    for(int i = 0; i < k; i++)
        a[i + left] = temp[i];

    delete[] temp;
}

void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right)/2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, right);
        Merge(a, left, m, right);
    }
}

int main()
{
    ios::sync_with_stdio(false);

    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    cin >> N >> K >> S;
    for(int i = 0; i < N; i++)
        cin >> Screw[i];

    // Sắp xếp mảng của các hộp theo thứ tự số lượng đinh giảm dần
    // Mình dùng Merge Sort vì nó chạy nhanh, và mình cũng quen với việc triển khai nó
    // tuy nhiên bạn có thể dùng thuật toán sắp xếp khác.
    MergeSort(Screw, 0, N-1);

    int sum = 0;

    // Số lượng đinh cần thiết cho S cái bàn
    int need = K * S;

    // Chọn lần lượt từ các hộp đinh có số lượng đinh nhiều nhất trước
    // Cho đến khi nào đủ số lượng thì thôi
    int num;
    for(num = 0; num < N; num++)
    {
        if(sum >= need) break;
        else sum += Screw[num];
    }

    cout << num << 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é:

Spoj
Greedy