AE1B_2.cpp

#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
    // Tôi dùng Merge Sort vì nó chạy nhanh, và tôi 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;
}