查找购买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