मान लीजिए हमारे पास ratings नामक संख्याओं की एक सूची दी गई है, जो कोडर्स के प्रदर्शन स्कोर दिखाती है। अब मैनेजर हर कोडर को 1000 रुपये देना चाहता है, सिवाय इसके कि यदि दो कोडर आसन्न हैं, तो वे बेहतर प्रदर्शन करने वाले को खराब प्रदर्शन करने वाले से कम से कम 1000 रुपये अधिक देना चाहेंगे। हमें उपरोक्त प्रतिबंधों का पालन करते हुए मैनेजर द्वारा भुगतान की जा सकने वाली न्यूनतम राशि ढूंढनी है।
उदाहरण के लिए, यदि इनपुट ratings = [1, 2, 5, 1] है, तो आउटपुट 7000 होगा, क्योंकि प्रत्येक कोडर के लिए न्यूनतम भुगतान [1000, 2000, 3000, 1000] है।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (दो पास ग्रीडी):
pay := ratings के आकार की सूची, प्रारंभ में सभी 1।iको 1 सेlen(ratings)-1तक (बाएं से दाएं):यदि
ratings[i] > ratings[i-1], तोpay[i] = pay[i-1] + 1।
iकोlen(ratings)-2से 0 तक (दाएं से बाएं):यदि
ratings[i] > ratings[i+1], तोpay[i] = max(pay[i], pay[i+1] + 1)।
sum(pay) * 1000लौटाएं।
उदाहरण
class Solution: def solve(self, ratings): pay=[1 for _ in ratings] for i in range(1, len(ratings)): if ratings[i] > ratings[i-1]: pay[i] = pay[i-1]+1 for i in range(len(ratings)-2,-1,-1): if ratings[i] > ratings[i+1]: pay[i] = max(pay[i], pay[i+1]+1) return sum(pay)*1000 ob = Solution() ratings = [1, 2, 5, 1] print(ob.solve(ratings))
इनपुट
[1, 2, 5, 1]
आउटपुट
7000
