找到购买所有书籍的最低成本-yiteyi-C++库

给出了n本书的一系列评分。找到购买具有以下条件的所有书籍的最低成本：

null

每本书的成本至少为1美元。
如果评级高于相邻书籍，则一本书的成本高于相邻书籍（左或右）。

例如：

Input : Ratings[] = {1, 3, 4, 3, 7, 1}Output : 10Exp :- 1 + 2 + 3 + 1 + 2 + 1 = 10Input : ratings[] = {1, 6, 8, 3, 4, 1, 5, 7}Output : 15Exp :- 1 + 2 + 3 + 1 + 2 + 1 + 2 + 3 = 15

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

将两个数组left2right和right2left填入1。
从左向右遍历并填充left2right数组，并通过查看给定数组的先前评级来更新它。不要在意给定阵列的下一个等级。
从右向左遍历并填充right2left数组，并通过查看给定数组的下一个等级来更新它。不要在意给定阵列的先前评级。
找到两个数组中第i个位置的最大值（left2right和right2left），并将其添加到结果中

min_cost

C++

                         // C++ program to find minimum cost to buy                       
                         // n books.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     minCost(                                     int                                     ratings[],                                     int                                     n)                       
                         {                       
                                                 int                                     res = 0;                       
                                                 int                                     left2right[n];                       
                                                 int                                     right2left[n];                       
           
                                                 // fill 1 in both array                       
                                                 fill_n(left2right, n, 1);                       
                                                 fill_n(right2left, n, 1);                       
           
                                                 // Traverse from left to right and assign                       
                                                 // minimum possible rating considering only                       
                                                 // left adjacent                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 if                                     (ratings[i] > ratings[i - 1])                       
                                                 left2right[i] = left2right[i - 1] + 1;                       
           
                                                 // Traverse from right to left and assign                       
                                                 // minimum possible rating considering only                       
                                                 // right adjacent                       
                                                 for                                     (                                     int                                     i = n - 2; i >= 0; i--)                       
                                                 if                                     (ratings[i] > ratings[i + 1])                       
                                                 right2left[i] = right2left[i + 1] + 1;                       
                                   
                                                 // Since we need to follow rating rule for                       
                                                 // both adjacent, we pick maximum of two                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 res += max(left2right[i], right2left[i]);                       
                                   
                                                 return                                     res;                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };                       
                                                 int                                     n =                                     sizeof                                     (ratings) /                                     sizeof                                     (ratings[0]);                       
                                                 cout << minCost(ratings, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA Code For Find minimum cost to                       
                         // buy all books                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 public                                     static                                     int                                     minCost(                                     int                                     ratings[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     res =                                     0                                     ;                       
                                                 int                                     left2right[] =                                     new                                     int                                     [n];                       
                                                 int                                     right2left[] =                                     new                                     int                                     [n];;                       
                                   
                                                 // fill 1 in both array                       
                                                 Arrays.fill(left2right,                                     1                                     );                       
                                                 Arrays.fill(right2left,                                     1                                     );                       
                                   
                                                 // Traverse from left to right and assign                       
                                                 // minimum possible rating considering                       
                                                 // only left adjacent                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 if                                     (ratings[i] > ratings[i -                                     1                                     ])                       
                                                 left2right[i] = left2right[i -                                     1                                     ] +                                     1                                     ;                       
                                   
                                                 // Traverse from right to left and assign                       
                                                 // minimum possible rating considering only                       
                                                 // right adjacent                       
                                                 for                                     (                                     int                                     i = n -                                     2                                     ; i >=                                     0                                     ; i--)                       
                                                 if                                     (ratings[i] > ratings[i +                                     1                                     ])                       
                                                 right2left[i] = right2left[i +                                     1                                     ] +                                     1                                     ;                       
                                   
                                                 // Since we need to follow rating rule for                       
                                                 // both adjacent, we pick maximum of two                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 res += Math.max(left2right[i],                       
                                                 right2left[i]);                       
                                   
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     ratings[] = {                                     1                                     ,                                     6                                     ,                                     8                                     ,                                     3                                     ,                                     4                                     ,                                     1                                     ,                                     5                                     ,                                     7                                     };                       
                                                 int                                     n = ratings.length;                       
                                                 System.out.print(minCost(ratings, n));                       
                                   
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Arnav Kr. Mandal.                       

python

                         # Python program to find minimum cost to buy                       
                         # n books.                       
           
                         def                                     minCost(ratings, n):                       
                                                 res                                     =                                     0                       
                                   
                                                 # fill 1 in both array                       
                                                 left2right                                     =                                     [                                     1                                     for                                     i                                     in                                     range                                     (n)]                       
                                                 right2left                                     =                                     [                                     1                                     for                                     i                                     in                                     range                                     (n)]                       
                                   
                                                 # Traverse from left to right and assign                       
                                                 # minimum possible rating considering only                       
                                                 # left adjacent                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 if                                     (ratings[i] > ratings[i                                     -                                     1                                     ]):                       
                                                 left2right[i]                                     =                                     left2right[i                                     -                                     1                                     ]                                     +                                     1                       
                                   
                                                 # Traverse from right to left and assign                       
                                                 # minimum possible rating considering only                       
                                                 # right adjacent                       
                                                 i                                     =                                     n                                     -                                     2                       
                                                 while                                     (i >                                     =                                     0                                     ):                       
                                                 if                                     (ratings[i] > ratings[i                                     +                                     1                                     ]):                       
                                                 right2left[i]                                     =                                     right2left[i                                     +                                     1                                     ]                                     +                                     1                       
                                                 i                                     -                                     =                                     1                       
                                   
                                                 # Since we need to follow rating rule for                       
                                                 # both adjacent, we pick maximum of two                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 res                                     +                                     =                                     max                                     (left2right[i], right2left[i])                       
                                   
                                                 return                                     res                       
                                   
                         # Driver function                       
                         ratings                                     =                                     [                                     1                                     ,                                     6                                     ,                                     8                                     ,                                     3                                     ,                                     4                                     ,                                     1                                     ,                                     5                                     ,                                     7                                     ]                       
                         n                                     =                                     len                                     (ratings)                       
                         print                                     minCost(ratings, n)                       
           
                         # This code is contributed by Sachin Bisht                       

C#

                         // C# code For Finding minimum                       
                         // cost to buy all books                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 public                                     static                                     int                                     minCost(                                     int                                     []ratings,                                     int                                     n)                       
                                                 {                       
                                                 int                                     res = 0;                       
                                                 int                                     []left2right =                                     new                                     int                                     [n];                       
                                                 int                                     []right2left =                                     new                                     int                                     [n];                       
                                   
                                                 // fill 1 in both array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 left2right[i] = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 right2left[i] = 1;                       
                                   
                                                 // Traverse from left to right and assign                       
                                                 // minimum possible rating considering                       
                                                 // only left adjacent                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 if                                     (ratings[i] > ratings[i - 1])                       
                                                 left2right[i] = left2right[i - 1] + 1;                       
                                   
                                                 // Traverse from right to left and assign                       
                                                 // minimum possible rating considering only                       
                                                 // right adjacent                       
                                                 for                                     (                                     int                                     i = n - 2; i >= 0; i--)                       
                                                 if                                     (ratings[i] > ratings[i + 1])                       
                                                 right2left[i] = right2left[i + 1] + 1;                       
                                   
                                                 // Since we need to follow rating rule for                       
                                                 // both adjacent, we pick maximum of two                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 res += Math.Max(left2right[i],                       
                                                 right2left[i]);                       
                                   
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []ratings = {1, 6, 8, 3, 4, 1, 5, 7};                       
                                                 int                                     n = ratings.Length;                       
                                                 Console.Write(minCost(ratings, n));                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by nitin mittal.                       

Javascript

                         <script>                       
           
                         // JavaScript program to find minimum cost to buy                       
                         // n books.                       
           
                         function                                     minCost(ratings, n) {                       
                                                 let res = 0;                       
                                                 let left2right =                                     new                                     Array(n).fill(1);                       
                                                 let right2left =                                     new                                     Array(n).fill(1);                       
           
           
                                                 // Traverse from left to right and assign                       
                                                 // minimum possible rating considering only                       
                                                 // left adjacent                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 if                                     (ratings[i] > ratings[i - 1])                       
                                                 left2right[i] = left2right[i - 1] + 1;                       
           
                                                 // Traverse from right to left and assign                       
                                                 // minimum possible rating considering only                       
                                                 // right adjacent                       
                                                 for                                     (let i = n - 2; i >= 0; i--)                       
                                                 if                                     (ratings[i] > ratings[i + 1])                       
                                                 right2left[i] = right2left[i + 1] + 1;                       
           
                                                 // Since we need to follow rating rule for                       
                                                 // both adjacent, we pick maximum of two                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 res += Math.max(left2right[i], right2left[i]);                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver function                       
           
                         let ratings = [1, 6, 8, 3, 4, 1, 5, 7];                       
                         let n = ratings.length;                       
                         document.write(minCost(ratings, n));                       
           
                         </script>                       

输出：

时间复杂性–O（n）辅助空间–O（n）本文由 哈希特·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章