資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C語言中可以購買的糖果最大數量
給定一個長度儲存在“size”中的糖果陣列 candies[]。每個元素 candies[i] 代表 i 型別糖果的數量。目標是儘可能多地購買任何金額的糖果。條件如下：
如果你購買 X[i] 個 i 型別糖果 (0<= X[i] <= candies[i] )，那麼對於所有 j ( 1<=j<=i )，至少滿足以下條件之一：
X(j) < X(i) (購買的 j 型別糖果數量少於 i 型別糖果數量)
X(j)=0，沒有購買 j 型別糖果
讓我們透過例子來理解。
輸入 − Arr[] = { 1,3,5,2,6,7 }.
輸出 − 可以購買的糖果最大數量 − 16
說明 − 購買的 i 型別糖果數量 { 0,3,5,2,6,0 }
輸入 − Arr[] = { 5,7,7,3,4 }.
輸出 − 可以購買的糖果最大數量 − 10
說明 − 購買的 i 型別糖果數量 { 0,0,7,3,0 }
下面程式中使用的演算法如下
整數陣列 candies[] 用於儲存 i 型別糖果的數量。
變數“size”儲存陣列 candies 的長度。
函式 maxCandies(int arr[], int n) 用於返回可以購買的糖果總數。
首先假設我們購買了最後一種型別的糖果。bought=arr[n-1]
從倒數第二個元素開始，for(i=n-2;i>=0;i--)
變數 x 儲存可以購買的當前型別糖果的數量。x=arr[i] 或 bought-1，取較小者。
如果 x 不為零，則將其新增到總和中。
如果總和大於之前的 bought 值，則 bought=x。
返回 bought 結果。
示例
#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
更新於：2020年8月17日
705 次瀏覽
廣告