数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在C++中查找购买所有书籍的最低成本
假设我们有一个包含n个元素的数组。这些是它们的评分。在以下条件下，找到购买所有书籍的最低成本：
- 每本书的成本至少为1美元
- 如果评分高于相邻评分，则一本书的成本高于其相邻书籍（左侧或右侧）。
例如，如果评分数组为[1, 3, 4, 3, 7, 1]，则输出为10，因为1 + 2 + 3 + 1 + 2 + 1 = 10
为了解决这个问题，我们必须创建两个数组，称为LtoR和RtoL，并用1填充它们，然后按照以下步骤操作：
- 从左到右遍历，然后填充LtoR，并通过查看给定数组的先前评分来更新它。我们不关心给定数组的下一个评分。
- 从右到左遍历，然后填充RtoL，并通过查看给定数组的先前评分来更新它。我们不关心给定数组的下一个评分。
- 对于LtoR和RtoL两个数组中第i个位置的最大值，将其添加到结果中。
示例
#include<iostream>
using namespace std;
int getMinCost(int ratings[], int n) {
int res = 0;
int LtoR[n];
int RtoL[n];
for(int i = 0; i<n; i++){
LtoR[i] = RtoL[i] = 1;
}
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
LtoR[i] = LtoR[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1])
RtoL[i] = RtoL[i + 1] + 1;
for (int i = 0; i < n; i++)
res += max(LtoR[i], RtoL[i]);
return res;
}
int main() {
int ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };
int n = sizeof(ratings) / sizeof(ratings[0]);
cout << "Minimum cost is: " << getMinCost(ratings, n);
}输出
Minimum cost is: 15
更新于：2019年12月18日
196次浏览
广告