Phân phối bóng không trùng màu cho học sinh trong C++

Giới thiệu

Cho n quả bóng có các màu khác nhau (biểu diễn bằng chuỗi ký tự) và k học sinh. Phân phối bóng sao cho không học sinh nào nhận 2 quả bóng cùng màu. Kiểm tra xem có phân phối được không.

Điều kiện cần và đủ

Phân phối được ⇔ Số lượng bóng của mỗi màu ≤ k (số học sinh).

Vì mỗi học sinh chỉ nhận tối đa 1 quả mỗi màu, nên nếu một màu xuất hiện > k lần thì chắc chắn có học sinh nhận trùng màu.

Ví dụ

n = 10, k = 5, ballsColors = "rrrgbrbgbr"

• r: 4 lần ≤ 5 ✓
• g: 2 lần ≤ 5 ✓
• b: 4 lần ≤ 5 ✓

Mã nguồn hoàn chỉnh

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

bool canDistributeBalls(string ballsColors, int n, int k) {
    unordered_map<char, int> colorCount;
    
    // Đếm số lượng mỗi màu
    for (int i = 0; i < n; i++) {
        colorCount[ballsColors[i]]++;
    }
    
    // Kiểm tra điều kiện
    for (auto &pair : colorCount) {
        if (pair.second > k) {
            return false;
        }
    }
    return true;
}

int main() {
    int n = 10, k = 5;
    string ballsColors = "rrrgbrbgbr";
    
    if (canDistributeBalls(ballsColors, n, k)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Kết quả chạy chương trình

Yes

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

• Thời gian: O(n) - duyệt chuỗi một lần
• Không gian: O(m) - m là số màu khác nhau (tối đa 26 nếu chỉ chữ cái)

Cải tiến: Sử dụng mảng thay vì map

Nếu màu chỉ là chữ cái thường 'a'-'z':

bool canDistributeBallsOptimized(string ballsColors, int n, int k) {
    int count[26] = {0};
    for (char c : ballsColors) {
        count[c - 'a']++;
        if (count[c - 'a'] > k) return false; // Sớm thoát
    }
    return true;
}

Mở rộng: In cách phân phối cụ thể

vector<vector<char>> distributeBalls(string ballsColors, int n, int k) {
    vector<vector<char>> students(k);
    unordered_map<char, int> colorIndex; // Màu → học sinh tiếp theo nhận
    
    for (char c : ballsColors) {
        int student = colorIndex[c] % k;
        students[student].push_back(c);
        colorIndex[c]++;
    }
    return students;
}

Kết luận

Bài toán ứng dụng nguyên lý Dirichlet (pigeonhole principle): nếu có hòn कबूतर (bóng cùng màu) > lỗ कबूतर (học sinh) thì ít nhất một lỗ chứa ≥ 2 कबूतर.