मान लीजिए कि हमारे पास n तत्वों की एक सरणी है। ये उनकी रेटिंग हैं। निम्नलिखित शर्त के साथ सभी पुस्तकों को खरीदने के लिए न्यूनतम लागत ज्ञात कीजिए -
- प्रत्येक पुस्तक की कीमत कम से कम 1 डॉलर होगी
- एक किताब की कीमत बगल वाले (बाएं या दाएं) से ज्यादा होती है, अगर रेटिंग बगल वाले से ज्यादा है।
तो उदाहरण के लिए, यदि रेटिंग सरणी [1, 3, 4, 3, 7, 1] की तरह है, तो आउटपुट 10 है, जैसे 1 + 2 + 3 + 1 + 2 + 1 =10
इसे हल करने के लिए, हमें LtoR, और RtoL नामक दो सरणियाँ बनानी होंगी, और उन्हें 1 से भरना होगा, अब इन चरणों का पालन करें -
- बाएं से दाएं पार करें, फिर एलटीओआर भरें, और दिए गए सरणी की पिछली रेटिंग देखकर इसे अपडेट करें। हम दिए गए सरणी की अगली रेटिंग की परवाह नहीं कर रहे हैं
- दाएं से बाएं ट्रैवर्स करें, फिर RtoL भरें, और दिए गए एरे की पिछली रेटिंग देखकर इसे अपडेट करें। हम दिए गए सरणी की अगली रेटिंग की परवाह नहीं कर रहे हैं
- एलटीओआर और आरटीओएल दोनों सरणी में ith स्थिति के अधिकतम मूल्य के लिए, फिर इसे परिणाम में जोड़ें।
उदाहरण
#include<iostream>
using namespace std;
int getMinCost(int ratings[], int n) {
int res = 0;
int LtoR[n];
int RtoL[n];
for(int i = 0; i<n; i++){
LtoR[i] = RtoL[i] = 1;
}
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
LtoR[i] = LtoR[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1])
RtoL[i] = RtoL[i + 1] + 1;
for (int i = 0; i < n; i++)
res += max(LtoR[i], RtoL[i]);
return res;
}
int main() {
int ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };
int n = sizeof(ratings) / sizeof(ratings[0]);
cout << "Minimum cost is: " << getMinCost(ratings, n);
} आउटपुट
Minimum cost is: 15