เราได้รับอาร์เรย์ของขนม[]ของความยาวที่จัดเก็บใน 'ขนาด' ลูกอมแต่ละธาตุ [i] มีหมายเลขสำหรับลูกอมประเภท i เป้าหมายคือซื้อลูกอมให้ได้มากที่สุดสำหรับเงินจำนวนเท่าใดก็ได้ เงื่อนไขเป็นไปตามที่กำหนด -
หากคุณซื้อ X[i] ประเภท i (0<=X[i] <=candies[i] ) ดังนั้นสำหรับ j ทั้งหมด ( 1<=j<=i ) อย่างน้อยในเงื่อนไขต่อไปนี้จะต้องเป็นจริง:
-
X(j)
-
X(j)=0, ไม่ได้ซื้อลูกอมประเภท j
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − Arr[] ={ 1,3,5,2,6,7 }.
ผลผลิต − Candies สูงสุดที่สามารถซื้อได้ − 16
คำอธิบาย − ลูกอมที่ซื้อประเภท i { 0,3,5,2,6,0 }
ป้อนข้อมูล − Arr[] ={ 5,7,7,3,4 }.
ผลผลิต − Candies สูงสุดที่สามารถซื้อได้ − 10
คำอธิบาย − ลูกอมที่ซื้อประเภท i { 0,0,7,3,0 }
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
แคนดี้อาร์เรย์จำนวนเต็ม[] ใช้เพื่อเก็บจำนวนแคนดี้ประเภท i
-
'ขนาด' ตัวแปรเก็บความยาวของลูกอมอาร์เรย์
-
ฟังก์ชัน maxCandies(int arr[], int n) ใช้เพื่อส่งคืนจำนวนลูกอมทั้งหมดที่ซื้อได้
-
ก่อนอื่น สมมติว่าเราซื้อลูกอมชนิดสุดท้าย buy=arr[n-1]
-
เริ่มจากองค์ประกอบสุดท้ายที่สอง for(i=n-2;i>=0;i--)
-
ตัวแปร x เก็บจำนวนลูกอมประเภทปัจจุบันที่สามารถซื้อได้ x=arr[i] หรือ buy-1 แล้วแต่จำนวนใดจะน้อยกว่า
-
ถ้า x ไม่ใช่ซีโอ ให้บวกค่านี้กับผลรวม
-
หากยอดรวมมากกว่ามูลค่าที่ซื้อครั้งก่อน ให้ซื้อ=x
-
ส่งคืนผลลัพธ์ที่ซื้อ
ตัวอย่าง
#include <stdio.h>
int maxCandies(int arr[], int n){
int bought = arr[n - 1];
int total = bought;
// Starting from second last
for (int i = n - 2; i >= 0; i--) {
// Amount of candies of the current
// type that can be bought
int x = arr[i]<bought-1?arr[i]:bought-1;
if (x >= 0) {
total += x;
bought = x;
}
}
return total;
}
int main(){
int candies[] = { 1,2,4,3,7 };
int size = 5;
printf("Total Candies that can be bought: %d", maxCandies(candies, size));
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Total Candies that can be bought: 13
