แคนดี้ในภาษา C++

สมมุติว่ามีเด็ก N คน กำลังยืนเข้าแถว ที่นี่เด็กแต่ละคนจะได้รับการกำหนดค่าการให้คะแนน เรากำลังจัดหาขนมให้กับเด็กเหล่านี้ภายใต้ข้อกำหนดดังต่อไปนี้ -

• เด็กแต่ละคนต้องมีขนมอย่างน้อยหนึ่งชิ้น

• เด็กที่มีคะแนนสูงจะได้รับขนมมากกว่าเพื่อนบ้าน

เราต้องหาจำนวนขนมขั้นต่ำที่เราต้องให้หรือไม่

ดังนั้นหากอินพุตเป็น [1,1,3] ผลลัพธ์จะเป็น 4 ดังนั้นพวกเขาจะได้รับลูกอม 1, 1 และ 2 ตามลำดับ

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

• n :=ขนาดของการจัดเรตอาร์เรย์ สร้างอาร์เรย์ที่เรียกว่า dp ขนาด n เติมโดยใช้ 1

• ยกเลิก :=0

• สำหรับฉันอยู่ในช่วง 1 ถึง n – 1

  • ถ้าการให้คะแนน[i]> การให้คะแนน[i – 1] แล้ว dp[i] :=dp[i - 1] + 1

• สำหรับฉันอยู่ในช่วง n - 2 เหลือ 0

  • หากการให้คะแนน[i]> การให้คะแนน[i + 1] ดังนั้น dp[i] :=สูงสุดของ dp[i] และ dp[i + 1] + 1

• ret :=ผลรวมขององค์ประกอบของ dp

• รีเทิร์น

ตัวอย่าง (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int candy(vector<int>& ratings) {
      int n = ratings.size();
      vector <int> dp(n, 1);
      int ret = 0;
      for(int i = 1; i < n; i++){
         if(ratings[i] > ratings[i - 1]){
            dp[i] = dp[i - 1] + 1;
         }
      }
      for(int i = n - 2; i >= 0; i--){
         if(ratings[i] > ratings[i + 1]){
            dp[i] = max(dp[i], dp[i + 1] + 1);
         }
      }
      for(int i = 0; i < n; i+=1){
         ret += dp[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,3};
   cout << (ob.candy(v));
}

อินพุต

[1,1,3]

ผลลัพธ์

4