मान लीजिए कि N बच्चे हैं, वे एक पंक्ति में खड़े हैं। यहां प्रत्येक बच्चे को एक रेटिंग मान दिया जाता है। हम इन बच्चों को निम्नलिखित आवश्यकताओं के अधीन कैंडी की आपूर्ति कर रहे हैं -
-
प्रत्येक बच्चे के पास कम से कम एक कैंडी होनी चाहिए।
-
जिन बच्चों की रेटिंग अधिक है, उन्हें अपने पड़ोसियों की तुलना में अधिक कैंडी मिलेगी।
हमें कैंडीज की न्यूनतम संख्या ज्ञात करनी होगी जो हमें देनी चाहिए?
तो अगर इनपुट [1,1,3] जैसा है, तो आउटपुट 4 होगा। तो उन्हें क्रमशः 1, 1 और 2 कैंडी मिलेंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n:=सरणी रेटिंग का आकार, आकार n का dp नामक सरणी बनाएं, इसे 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
-
-
रिट:=डीपी के तत्वों का योग
-
वापसी रिट
उदाहरण (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