C++のキャンディー

N人の子供がいて、並んでいるとします。ここでは、各子に評価値が割り当てられています。以下の要件を満たしたこれらの子供たちにキャンディーを供給しています-

• 各子供は少なくとも1つのキャンディーを持っている必要があります。

• 評価が高い子供は、隣人よりも多くのキャンディーを手に入れます。

与える必要のあるキャンディーの最小数を見つける必要がありますか？

したがって、入力が[1,1,3]の場合、出力は4になります。したがって、それぞれ1、1、2個のキャンディーが得られます。

これを解決するには、次の手順に従います-

• n：=配列の評価のサイズ、サイズnのdpという配列を作成し、1を使用してこれを埋めます

• ret：=0

• 1からn–1の範囲のiの場合

  • 評価[i]>評価[i– 1]の場合、dp [i]：=dp [i-1] + 1

• n-2から0までの範囲のiの場合

  • 評価[i]>評価[i+1]の場合、dp [i]：=dp[i]とdp[i+ 1]+1の最大値

• ret：=dpの要素の合計

• retを返す

例（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