สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอีกค่าหนึ่งคือ d ชาวนาได้จัดเตรียมหญ้าแห้งไว้ในบริษัทแล้ว กอง ith ประกอบด้วยก้อนหญ้าแห้ง A[i] ทุกวันวัวสามารถเลือกที่จะย้ายกองหญ้าแห้งหนึ่งกองไปยังกองที่อยู่ติดกัน วัวสามารถทำได้ในวันที่ไม่ทำอะไรเลย วัวต้องการเพิ่มก้อนหญ้าแห้งในกองแรกใน d วัน เราต้องนับก้อนหญ้าแห้งสูงสุดกองแรก
ดังนั้นหากอินพุตเป็นเช่น d =5; A =[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
