แจกลูกบอลไม่ให้ซ้ำสีใน C++

บทนำ

โจทย์: มี n ลูกบอลสีต่างๆ แจกให้นักเรียน k คน โดยแต่ละคนต้องไม่ได้รับลูกบอลสีซ้ำกัน (คือ สีใดสีหนึ่ง ต่อคนได้สูงสุด 1 ลูก)

เงื่อนไขการแจกได้

สำหรับทุกสี จำนวนลูกบอลสีนั้นต้อง ≤ k (จำนวนนักเรียน) มิฉะนั้นจะมีคนได้สีซ้ำแน่นอน

ขั้นตอนการแก้ปัญหา

1. นับจำนวนลูกบอลแต่ละสี (ใช้ map)
2. ตรวจสอบทุกสี: ถ้ามีสีไหนมากกว่า k → แจกไม่ได้ (No)
3. ถ้าทุกสี ≤ k → แจกได้ (Yes)

ตัวอย่างโค้ด

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

bool canDistributeBalls(string ballsColors, int n, int k) {
    map<char, int> charCount;
    for (int i = 0; i < n; i++) {
        charCount[ballsColors[i]]++;
    }
    for (auto itr = charCount.begin(); itr != charCount.end(); itr++) {
        if (itr->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;
}

ผลลัพธ์

Yes

คำอธิบายตัวอย่าง

สี: r=4, g=2, b=4 | นักเรียน k=5 | ทุกสี ≤ 5 → แจกได้

สรุป

นหลักการ Pigeonhole Principle: หากมีสีใดมากกว่าจำนวนคน ต้องมีคนได้สีซ้ำแน่นอน โค้ด O(n log n) เนื่องจากใช้ map