मान लीजिए हमारे पास n तत्वों की एक सरणी A और एक अन्य मान d है। एक किसान ने फर्म पर n हे-बेल ढेर व्यवस्थित किए हैं। iवें ढेर में A[i] हे-बेल हैं। हर दिन एक गाय किसी भी ढेर में एक हे-बेल को आसन्न ढेर में ले जाना चुन सकती है। गाय एक दिन में ऐसा कर सकती है अन्यथा कुछ नहीं कर सकती। गाय d दिनों में पहले ढेर में हे-बेल को अधिकतम करना चाहती है। हमें पहले ढेर पर हे-बेल की अधिकतम संख्या गिननी है।
उदाहरण के लिए, यदि इनपुट d = 5; A = [1, 0, 3, 2] है, तो आउटपुट 3 होगा, क्योंकि पहले दिन तीसरे से दूसरे में ले जाएं, दूसरे दिन फिर तीसरे से दूसरे में, फिर अगले दो दिनों में दूसरे से पहले में ले जाएं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
a0 := A[0] n := size of A for initialize i := 1, when i < n, update (increase i by 1), do: ai := A[i] w := minimum of ai and d / i a0 := a0 + w d := d - w * i return a0
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(int d, vector A){ int a0 = A[0]; int n = A.size(); for (int i = 1; i < n; i++){ int ai = A[i]; int w = min(ai, d / i); a0 += w; d -= w * i; } return a0; } int main(){ int d = 5; vector A = { 1, 0, 3, 2 }; cout << solve(d, A) << endl; }
इनपुट
5, { 1, 0, 3, 2 }आउटपुट
3
