Distribute Candies trong C++

Cho mảng candies độ dài chẵn, mỗi số đại diện cho một loại kẹo. Cần chia đều số lượng kẹo cho hai người (em gái và anh trai) sao cho em gái nhận được số loại kẹo khác nhau nhiều nhất có thể.

Ví dụ: [1,1,2,3] → em gái nhận [2,3] (2 loại), anh trai nhận [1,1] (1 loại). Kết quả: 2.

Giải thuật

Số loại kẹo tối đa em gái có thể nhận = min(số loại kẹo khác nhau, tổng số kẹo / 2).

1. Dùng unordered_set để đếm số loại kẹo khác nhau.
2. Trả về min(set.size(), n/2).

Ví dụ triển khai C++

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

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> s(candies.begin(), candies.end());
        return min((int)s.size(), (int)candies.size() / 2);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,1,2,3};
    cout << ob.distributeCandies(v); // 2
    return 0;
}

Đầu vào / Đầu ra

Input: {1,1,2,3}
Output: 2