C++: Số đội 3 người tối đa từ nhóm 1 và 2 người

Bài toán: Mảng A: 1 = người đơn (ghép tự do), 2 = cặp (phải cùng đội hoặc cùng không). Ghép thành đội 3 người. Tối đa số đội.

Giải pháp: Đếm p = số 1, q = số 2.

• Mỗi cặp (2) cần 1 người đơn (1) → tạo min(p, q) đội.
• Người đơn dư = p - q (nếu p > q), gom 3 người/đội → thêm (p-q)/3 đội.
• Nếu p ≤ q: chỉ tạo được p đội (hết người đơn).

Code C++

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

int solve(vector<int> A) {
    int p = 0, q = 0;
    for (int x : A) (x == 1 ? p : q)++;
    if (p > q) return q + (p - q) / 3;
    return p;
}

int main() {
    vector<int> A = {2,2,2,1,1,1,1};
    cout << solve(A) << endl; // 3
    return 0;
}

Kết quả

3