สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ n นี่คือการให้คะแนนของพวกเขา ค้นหาต้นทุนขั้นต่ำในการซื้อหนังสือทุกเล่มโดยมีเงื่อนไขดังต่อไปนี้ −
- ราคาหนังสือแต่ละเล่มอย่างน้อย 1 ดอลลาร์
- หนังสือมีราคาสูงกว่าหนังสือที่อยู่ติดกัน (ซ้ายหรือขวา) หากการให้คะแนนมากกว่าที่อยู่ติดกัน
ตัวอย่างเช่น ถ้าเรตติ้งเป็นเช่น [1, 3, 4, 3, 7, 1] แล้วผลลัพธ์จะเป็น 10 เช่น 1 + 2 + 3 + 1 + 2 + 1 =10
เพื่อแก้ปัญหานี้ เราต้องทำสองอาร์เรย์ที่เรียกว่า LtoR และ RtoL และเติม 1 ลงในอาร์เรย์ ทำตามขั้นตอนเหล่านี้ -
- เลื่อนไปทางซ้ายไปขวา จากนั้นเติม LtoR และอัปเดตโดยดูการจัดอันดับก่อนหน้าของอาร์เรย์ที่ระบุ เราไม่ได้สนใจเรตติ้งถัดไปของอาร์เรย์ที่กำหนด
- ข้ามจากขวาไปซ้าย จากนั้นเติม RtoL และอัปเดตโดยดูการจัดอันดับก่อนหน้าของอาร์เรย์ที่ระบุ เราไม่ได้สนใจเรตติ้งถัดไปของอาร์เรย์ที่กำหนด
- สำหรับค่าสูงสุดของตำแหน่ง ith ในอาร์เรย์ LtoR และ RtoL แล้วเพิ่มลงในผลลัพธ์
ตัวอย่าง
#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
