資料結構
網路
關係型資料庫管理系統 (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次瀏覽
廣告