กำหนดคุกกี้ใน C++

สมมติว่าเรากำลังพยายามแจกจ่ายคุกกี้ให้กับเด็ก แต่เราควรให้คุกกี้แก่เด็กแต่ละคนไม่เกินหนึ่งคุกกี้ ตอนนี้เด็กแต่ละคนมีปัจจัยความโลภ gi ซึ่งเป็นขนาดต่ำสุดของคุกกี้ที่เด็กจะพอใจ และคุกกี้ j แต่ละตัวมีขนาด sj เมื่อ sj>=gi เราสามารถกำหนดคุกกี้ j ให้กับลูก i และลูก i จะพึงพอใจ เป้าหมายของเราคือเพิ่มจำนวนเนื้อหาย่อยให้มากที่สุดและส่งออกจำนวนสูงสุด

ดังนั้น หากอินพุตเป็น [1,2], [1,2,3] ผลลัพธ์จะเป็น 2 ลูกจะมี 2 ลูกและคุกกี้ 3 ตัว ปัจจัยความโลภของเด็ก 2 คนคือ 1, 2 ตอนนี้เรามีคุกกี้ 3 ชิ้นและขนาดของคุกกี้ก็ใหญ่พอที่จะทำให้เด็กๆ พอใจได้ทั้งหมด ดังนั้นผลลัพธ์ที่ได้คือ 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จัดเรียงอาร์เรย์ g

• เรียงลำดับอาร์เรย์ s

• ผม :=0, j =0

• ในขณะที่ (i <ขนาดของ g และ j <ขนาดของ s) ทำ −

  • ถ้า g[i] <=s[j] แล้ว −

    • (เพิ่ม i ขึ้น 1)

  • (เพิ่มขึ้น j โดย 1)

• กลับมา

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findContentChildren(vector<int>& g, vector<int>& s) {
      sort(g.begin(), g.end());
      sort(s.begin(), s.end());
      int i = 0, j = 0;
      while (i < g.size() && j < s.size()) {
         if (g[i] <= s[j])
            i++;
            j++;
         }
         return i;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2}, v1 = {1,2,3};
   cout << (ob.findContentChildren(v, v1));
}

อินพุต

{1,2}, {1,2,3}

ผลลัพธ์

2