Kẹo trong C ++

Giả sử có N trẻ em, chúng đang đứng trên một hàng. Ở đây mỗi đứa trẻ được gán một giá trị xếp hạng. Chúng tôi cung cấp kẹo cho những trẻ em này theo các yêu cầu sau -

• Mỗi đứa trẻ phải có ít nhất một viên kẹo.

• Những đứa trẻ có xếp hạng cao sẽ nhận được nhiều kẹo hơn những đứa trẻ hàng xóm.

Tìm số kẹo tối thiểu phải cho là bao nhiêu?

Vì vậy, nếu đầu vào là [1,1,3], thì đầu ra sẽ là 4. Vì vậy, họ sẽ nhận được 1, 1 và 2 viên kẹo tương ứng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của xếp hạng mảng, tạo mảng được gọi là dp có kích thước n, điền vào giá trị này bằng cách sử dụng 1

• ret:=0

• cho tôi trong phạm vi từ 1 đến n - 1

  • nếu xếp hạng [i]> xếp hạng [i - 1] thì dp [i]:=dp [i - 1] + 1

• đối với tôi trong phạm vi n - 2 xuống 0

  • nếu xếp hạng [i]> xếp hạng [i + 1], thì dp [i]:=max của dp [i] và dp [i + 1] + 1

• ret:=tổng các phần tử của dp

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,1,3]

Đầu ra

4