सी ++ कोड पहले ढेर पर अधिकतम घास-गांठों की गणना करने के लिए

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है और दूसरा मान d है। एक किसान ने फर्म पर n haybalepiles की व्यवस्था की है। Ith ढेर में A[i] घास की गांठें होती हैं। हर दिन एक गाय किसी भी ढेर में एक घास की गठरी को बगल के ढेर में ले जाने का विकल्प चुन सकती है। गाय इसे एक दिन में कर सकती है अन्यथा कुछ भी नहीं करती है। गाय पहले ढेर में घास की गांठों को d दिनों में अधिकतम करना चाहती है। हमें पहले ढेर पर घास की गांठों की अधिकतम संख्या गिननी है।

इसलिए, यदि इनपुट d =5 जैसा है; ए =[1, 0, 3, 2], तो आउटपुट 3 होगा, क्योंकि पहले दिन 3 से 2 तक, दूसरे दिन फिर से 3 से दूसरे पर, फिर अगले दो दिनों में, 2 से पहले पास करें।

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> 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<int> A = { 1, 0, 3, 2 };
   cout << solve(d, A) << endl;
}

इनपुट

5, { 1, 0, 3, 2 }

आउटपुट

3