Chúng ta được cung cấp một mảng kẹo [] có độ dài được lưu trữ trong ‘size’. Mỗi viên kẹo nguyên tố [i] có một số kẹo thuộc loại i, mục tiêu là mua nhiều kẹo nhất có thể với bất kỳ số tiền nào. Các điều kiện như đã cho -
Nếu bạn mua X [i] loại i (0 <=X [i] <=candy [i]), thì đối với tất cả j (1 <=j <=i) ít nhất trong các điều kiện sau phải đúng:
-
X (j)
-
X (j) =0, không có kẹo loại j nào được mua
Hãy cùng hiểu với các ví dụ.
Đầu vào - Arr [] ={1,3,5,2,6,7}.
Đầu ra - Số kẹo tối đa có thể mua - 16
Giải thích - Kẹo mua loại i {0,3,5,2,6,0}
Đầu vào - Arr [] ={5,7,7,3,4}.
Đầu ra - Số kẹo tối đa có thể mua - 10
Giải thích - Kẹo mua loại i {0,0,7,3,0}
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng số nguyên candy [] được sử dụng để lưu trữ số lượng kẹo thuộc loại i.
-
Biến 'kích thước' lưu trữ độ dài của kẹo mảng.
-
Hàm maxCandies (int arr [], int n) được sử dụng để trả về tổng số kẹo có thể mua được.
-
Đầu tiên, giả sử chúng ta đã mua loại kẹo cuối cùng. đã mua =arr [n-1]
-
Bắt đầu từ phần tử cuối cùng thứ hai, for (i =n-2; i> =0; i--)
-
Biến x lưu trữ số lượng kẹo của loại hiện tại có thể được mua. x =arr [i] hoặc đã mua-1, tùy theo giá trị nào ít hơn.
-
Nếu x không phải zeo thì cộng giá trị này vào tổng.
-
Nếu tổng số tiền nhiều hơn giá trị đã mua trước đó thì đã mua =x.
-
Trả lại kết quả đã mua.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Total Candies that can be bought: 13