Hiểu bài toán

Mario cần chọn một đoạn liên tiếp các cây nấm (trong dãy 10 cây) sao cho tổng giá trị của đoạn đó gần 100 nhất. Nếu có hai tổng giá trị cách 100 một khoảng bằng nhau (ví dụ 98 và 102), Mario sẽ chọn tổng giá trị lớn hơn (102).

Các cách tiếp cận

Cách Brute Force (Duyệt tất cả các đoạn)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[10];
    for(int i=0; i<10; i++) cin >> a[i];

    int best = 0;
    for(int i=0; i<10; i++) {
        int s = 0;
        for(int j=i; j<10; j++) {
            s += a[j];      
            if(abs(100-s) < abs(100-best)) best = s;
        }
    }

    cout << best;
}

• Time Complexity: O(N^2) (với N=10 là 100 phép tính)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Ta dùng hai vòng lặp lồng nhau: vòng lặp ngoài chọn điểm bắt đầu (i), vòng lặp trong chọn điểm kết thúc (j). Với mỗi cặp (i, j), ta tính tổng đoạn con từ i đến j. Nếu khoảng cách từ tổng này tới 100 nhỏ hơn khoảng cách của tổng tốt nhất hiện tại, ta cập nhật tổng tốt nhất. Độ phức tạp O(N^2) là hoàn toàn chấp nhận được với N=10.

Cách Brute Force (Cải tiến về điều kiện)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> mushrooms(10);
    for(int i=0;i<10;i++) cin >> mushrooms[i];

    int best_sum = 0;
    int best_diff = 1e9;

    for(int i=0;i<10;i++){
        int sum = 0;
        for(int j=i;j<10;j++){
            sum += mushrooms[j];
            int diff = abs(100 - sum);
            if(diff < best_diff || (diff == best_diff && sum > best_sum)){
                best_diff = diff;
                best_sum = sum;
            }
        }
    }

    cout << best_sum << "\n";
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(1)

Cách này tương tự cách đầu tiên nhưng xử lý rõ ràng hơn về trường hợp 'bằng nhau'. Thay vì chỉ so sánh khoảng cách, ta lưu cả khoảng cách tốt nhất (bestdiff) và tổng tốt nhất (bestsum). Nếu tìm thấy đoạn có khoảng cách nhỏ hơn, ta cập nhật cả hai. Nếu khoảng cách bằng nhau, ta chỉ cập nhật nếu tổng mới lớn hơn tổng cũ. Logic này đảm bảo đúng yêu cầu 'chọn tổng lớn hơn nếu bằng nhau'.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vì dãy chỉ có 10 phần tử nên độ phức tạp O(N^2) là tối ưu và dễ hiểu nhất.
• Bài toán yêu cầu tìm 'gần 100 nhất', nhưng nếu cách đều thì chọn số lớn hơn. Điều này có thể được xử lý bằng cách ưu tiên giảm khoảng cách (abs(100-sum)), và nếu bằng nhau thì ưu tiên tăng giá trị (sum).

Lỗi thường gặp

• Quên xử lý trường hợp hai tổng có khoảng cách bằng nhau (ví dụ 98 và 102 đều cách 100 là 2). Nếu chỉ so sánh abs(100-s) < abs(100-best), ta có thể chọn sai nếu duyệt không đúng thứ tự.
• Sử dụng biến lưu trữ tổng tạm thời không reset đúng cách giữa các lần lặp của vòng ngoài.