Hiểu bài toán

Bài toán yêu cầu chia dãy số gồm N viên bi (có số lượng a[i] và màu c[i]) vào các hộp sao cho:

1. Các hộp chỉ chứa bi cùng màu
2. Tổng số bi trong một hộp không vượt quá M
3. Bi phải được xếp theo đúng thứ tự xuất hiện ban đầu

Mục tiêu: Tìm số hộp tối thiểu cần dùng. Với mỗi viên bi, ta phải quyết định: hoặc bỏ vào hộp hiện tại (nếu cùng màu và còn chỗ), hoặc mở hộp mới.

Ví dụ: Nếu M=10, có 5 viên bi với a=[3,4,2,1,5], c=[1,1,2,2,1]. Ta có thể xếp: Hộp1: 3+4=7 (màu1), Hộp2: 2+1=3 (màu2), Hộp3: 5 (màu1) → Tổng 3 hộp. Không thể ít hơn vì màu1 bị ngắt quãng do màu2 xen vào.

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

Cách Giải thuật tham lam (Greedy)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("XepBi.inp", "r", stdin);
    freopen("XepBi.out", "w", stdout);

    int n;
    long long m;
    cin >> n >> m;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];

    long long current_sum = 0;
    int current_color = -1;
    int boxes = 0;

    for (int i = 0; i < n; i++) {
        // Nếu màu khác hoặc thêm vào sẽ vượt quá M
        if (c[i] != current_color || current_sum + a[i] > m) {
            boxes++;          // Mở hộp mới
            current_sum = a[i];
            current_color = c[i];
        } else {
            current_sum += a[i];  // Thêm vào hộp hiện tại
        }
    }

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

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận trực quan nhất:

1. Duyệt qua từng viên bi theo thứ tự

2. Với mỗi viên bi:

   • Nếu màu khác hộp hiện tại → Bắt buộc mở hộp mới
   • Nếu cùng màu nhưng thêm vào làm vượt M → Mở hộp mới
   • Ngược lại → Thêm vào hộp hiện tại

3. Ưu điểm: Đơn giản, chạy nhanh, chỉ cần 1 lần duyệt

4. Tính đúng đắn: Vì ta luôn cố gắng tận dụng hộp hiện tại khi có thể, chỉ mở hộp mới khi bất đắc dĩ, nên số hộp là tối thiểu.

Ví dụ chi tiết: M=10, a=[3,4,2,1,5], c=[1,1,2,2,1]

• i=0: Hộp1 (màu1), sum=3
• i=1: Cùng màu, 3+4=7≤10 → Hộp1, sum=7
• i=2: Màu khác → Hộp2 (màu2), sum=2
• i=3: Cùng màu, 2+1=3≤10 → Hộp2, sum=3
• i=4: Màu khác → Hộp3 (màu1), sum=5 → Kết quả: 3 hộp

Cách Giải thuật tham lam với kiểm tra lỗi

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("XepBi.inp", "r", stdin);
    freopen("XepBi.out", "w", stdout);

    long long n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<long long> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];

    long long s = 0, s1 = -1;
    int kq = 0;

    for (int i = 0; i < n; i++) {
        if (s1 == c[i] && s + a[i] <= m) {
            s += a[i];
        } else {
            kq++;
            s1 = c[i];
            s = a[i];
        }
    }

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

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là biến thể của giải thuật tham lam, viết cô đọng hơn:

• s: tổng số bi trong hộp hiện tại
• s1: màu của hộp hiện tại (-1 nghĩa là chưa có hộp)
• kq: số hộp đã dùng

Logic:

• Nếu cùng màu và còn chỗ → cộng dồn
• Ngược lại → tăng hộp, reset biến

Ưu điểm: Code ngắn, hiệu quả, xử lý được trường hợp hộp đầu tiên (khi s1=-1).

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

Bài học kinh nghiệm

• Vấn đề có cấu trúc 'greedy-choice property': quyết định tại mỗi bước lokal không ảnh hưởng xấu đến optimal solution
• Bài toán có thể xem là bài toán 'run-length encoding' có giới hạn dung lượng
• Mấu chốt là chỉ được phép mở hộp mới khi: (1) thay đổi màu, hoặc (2) hết dung lượng

Lỗi thường gặp

• Quên xử lý trường hợp hộp đầu tiên (s1=-1), có thể gây lỗi logic nếu viết sai điều kiện
• Sử dụng int thay vì long long cho biến t tổng số bi có thể gây overflow khi n hoặc m lớn
• Đặt tên biến không rõ ràng (s, s1, kq) làm giảm tính dễ đọc của code