Các Thẻ Thuật Toán

Mô Tả Vấn Đề

Bài toán yêu cầu tìm cách thu hoạch nhiều táo nhất với điều kiện cho trước.

Các tham số:
	1. n: Số lượng táo.
	2. a: Độ cao có thể đạt được thêm vào b.
	3. b: Độ cao ban đầu.
	4. s: Sức lực hiện tại.
	5. x: Độ cao cần để thu hoạch mỗi táo.
	6. y: Sức lực cần để thu hoạch mỗi táo.

Hiểu rõ các tham số trên, chúng ta có thể giải quyết bài toán bằng cách sử dụng thuật toán tham lam.

Logic chính:
	1. Tổng độ cao tối đa = a + b.
	2. Chỉ chọn những táo có độ cao nhỏ hơn hoặc bằng tổng độ cao tối đa.
	3. Chọn táo theo thứ tự sức lực cần thiết tăng dần.
	4. Dừng lại khi không còn đủ sức lực để thu hoạch thêm táo nào nữa.

Dựa trên logic này, chúng ta viết mã nguồn như sau:

Mã Nguồn AC

<!-- Sử dụng C++ -->
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> DataPair; // Định nghĩa kiểu dữ liệu chứa cả độ cao và sức lực

const int MAX_N = 5000;
DataPair apples[MAX_N];
vector<DataPair> validApples;
int result = 0;

int main() {
    int n, strength, heightA, heightB;
    cin >> n >> strength >> heightA >> heightB;
    int maxHeight = heightA + heightB;

    for(int i = 0; i < n; ++i) {
        cin >> apples[i].first >> apples[i].second; // Lấy giá trị độ cao và sức lực
    }

    for(int i = 0; i < n; ++i) {
        if(apples[i].first <= maxHeight) validApples.push_back(apples[i]);
    }

    sort(validApples.begin(), validApples.end(), [](DataPair a, DataPair b) {
        return a.second < b.second;
    });

    for(auto apple : validApples) {
        if(strength >= apple.second) {
            strength -= apple.second;
            result++;
        } else break;
    }

    cout << result;
    return 0;
}

Tuy nhiên, mã nguồn trên có thể được tối ưu hóa để giảm kích thước và tăng hiệu suất.

Mã Nguồn Tối Ưu

<!-- Sử dụng C++ -->
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> DataPair;
const int MAX_N = 5000;
vector<DataPair> allApples;
int result = 0;

int main() {
    int n, strength, heightA, heightB;
    cin >> n >> strength >> heightA >> heightB;
    int maxHeight = heightA + heightB;

    for(int i = 0; i < n; ++i) {
        int h, s;
        cin >> h >> s;
        allApples.push_back({h, s});
    }

    sort(allApples.begin(), allApples.end(), [](DataPair a, DataPair b) {
        return a.second < b.second;
    });

    for(auto apple : allApples) {
        if(apple.first <= maxHeight && strength >= apple.second) {
            strength -= apple.second;
            result++;
        }
    }

    cout << result;
    return 0;
}

Chúng ta cũng có thể sử dụng phương pháp khác như bucket sort để giải quyết bài toán.

Phương Pháp Bucket Sort

<!-- Sử dụng C++ -->
#include <iostream>

using namespace std;

const int MAX_N = 110;
const int MAX_STRENGTH = 100;
int arr[MAX_STRENGTH];

int main() {
    int n, strength, heightA, heightB;
    cin >> n >> strength >> heightA >> heightB;
    int maxHeight = heightA + heightB;

    for(int i = 0; i < n; ++i) {
        int h, s;
        cin >> h >> s;
        if(h <= maxHeight) arr[s]++;
    }

    int result = 0;
    for(int i = 0; i <= MAX_STRENGTH; ++i) {
        while(arr[i]-- > 0 && strength >= i) {
            strength -= i;
            result++;
        }
    }

    cout << result;
    return 0;
}