数据结构
网络
关系数据库管理系统 (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 次浏览
广告