Distribute Candies ใน C++

แนวคิด

สมมติว่ามีอาร์เรย์ความยาวคู่ ตัวเลขต่างๆ แทนชนิดลูกอมต่างๆ ตัวเลขแต่ละตัวคือลูกอมหนึ่งลูกของชนิดนั้น ต้องแจกลูกอมเท่ากันให้พี่น้อง ต้องหาจำนวนชนิดลูกอมสูงสุดที่น้องสาวได้รับ

เช่น ถ้าอินพุตคือ [1,1,2,3] ผลลัพธ์คือ 2 เพราะถ้าน้องสาวได้ [2,3] และพี่ชายได้ [1,1] น้องสาวมี 2 ชนิด พี่ชายมี 1 ชนิด

วิธีแก้:

• กำหนดเซต s
• วนลูป i := 0 ถึงขนาด candies - 1: แทรก candies[i] ลง s
• คืนค่า min ของขนาด s และขนาด candies / 2

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> s;
        for (int i = 0; i < candies.size(); i++)
            s.insert(candies[i]);
        return min(s.size(), candies.size() / 2);
    }
};
main() {
    Solution ob;
    vector<int> v = {1,1,2,3};
    cout << (ob.distributeCandies(v));
}

อินพุต

{1,1,2,3}

เอาต์พุต

2