โค้ด C++ นับฟางสูงสุดบนกองแรก

สมมติว่าเรามีอาร์เรย์ A ขนาด n และค่า d เกษตรกรจัดกองฟาง n กอง กองที่ i มี A[i] ฟาง ทุกวันวัวเลือกย้ายฟาง 1 หน่วยจากกองหนึ่งไปกองติดกันได้ วัวทำได้วันละครั้งหรือไม่ทำก็ได้ ต้องการเพิ่มฟางในกองแรกสูงสุดใน d วัน หาฟางสูงสุดบนกองแรก

เช่น ถ้าอินพุตคือ d = 5; A = [1, 0, 3, 2] เอาต์พุตจะเป็น 3 เพราะวันแรกย้ายจากกอง 3 ไป 2 วันที่สองอีกครั้ง วันที่ 3-4 ย้ายจาก 2 ไป 1

ขั้นตอนการแก้ปัญหา

a0 := A[0]
n := ขนาดของ A
for i := 1 ถึง n-1:
    ai := A[i]
    w := min(ai, 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 }