通过移除较大的阵列对使阵列大小为1的最低成本-yiteyi-C++库

给定一个由n个整数组成的数组。我们需要将阵列的大小减少到一个。我们可以选择一对整数，去掉其中较大的一个。这会将数组大小减少1。这个操作的成本等于较小操作的价值。找出将数组转换为单个元素所需的最低操作成本总和。 例如：

null

Input: 4 3 2 Output: 4Explanation: Choose (4, 2) so 4 is removed, new array = {2, 3}. Now choose (2, 3) so 3 is removed. So total cost = 2 + 2 = 4Input: 3 4Output: 3Explanation: choose 3, 4, so cost is 3.

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

其思想是始终选择最小值作为配对的一部分，并删除较大的值。这样可以最大限度地降低将阵列缩小到1的成本。以下是上述方法的实施情况：

CPP

                         // CPP program to find minimum cost to                       
                         // reduce array size to 1,                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to calculate the minimum cost                       
                         int                                     cost(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 // Minimum cost is n-1 multiplied with                       
                                                 // minimum element.                       
                                                 return                                     (n - 1) * (*min_element(a, a + n));                       
                         }                       
           
                         // driver program to test the above function.                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 4, 3, 2 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 cout << cost(a, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum cost                       
                         // to reduce array size to 1,                       
                         import                                     java.lang.*;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 // function to calculate the                       
                                                 // minimum cost                       
                                                 static                                     int                                     cost(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                                 int                                     min = a[                                     0                                     ];                       
                                   
                                                 // find the minimum using                       
                                                 // for loop                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i< a.length; i++)                       
                                                 {                       
                                                 if                                     (a[i] < min)                       
                                                 min = a[i];                       
                                                 }                       
                                   
                                                 // Minimum cost is n-1 multiplied                       
                                                 // with minimum element.                       
                                                 return                                     (n -                                     1                                     ) * min;                       
                                                 }                       
                                   
                                                 // driver program to test the                       
                                                 // above function.                       
                                                 static                                     public                                     void                                     main (String[] args)                       
                                                 {                       
                                   
                                                 int                                     []a = {                                     4                                     ,                                     3                                     ,                                     2                                     };                       
                                                 int                                     n = a.length;                       
                                   
                                                 System.out.println(cost(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by parashar.                       

Python3

                         # Python program to find minimum                       
                         # cost to reduce array size to 1                       
           
                         # function to calculate the                       
                         # minimum cost                       
                         def                                     cost(a, n):                       
           
                                                 # Minimum cost is n-1 multiplied                       
                                                 # with minimum element.                       
                                                 return                                     ( (n                                     -                                     1                                     )                                     *                                     min                                     (a) )                       
           
           
                         # driver code                       
                         a                                     =                                     [                                     4                                     ,                                     3                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (a)                       
                         print                                     (cost(a, n))                       
           
                         # This code is contributed by                       
                         # Smitha Dinesh Semwal                       

C#

                         // C# program to find minimum cost to                       
                         // reduce array size to 1,                       
                         using                                     System;                       
                         using                                     System.Linq;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 // function to calculate the minimum cost                       
                                                 static                                     int                                     cost(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Minimum cost is n-1 multiplied with                       
                                                 // minimum element.                       
                                                 return                                     (n - 1) * a.Min();                       
                                                 }                       
                                   
                                                 // driver program to test the above function.                       
                                                 static                                     public                                     void                                     Main (){                       
                                   
                                                 int                                     []a = { 4, 3, 2 };                       
                                                 int                                     n = a.Length;                       
                                   
                                                 Console.WriteLine(cost(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find minimum cost to                       
                         // reduce array size to 1,                       
           
                         // function to calculate                       
                         // the minimum cost                       
                         function                                     cost(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // Minimum cost is n-1                       
                                                 // multiplied with                       
                                                 // minimum element.                       
                                                 return                                     (                                     $n                                     - 1) * (min(                                     $a                                     ));                       
                         }                       
           
                                                 // Driver Code                       
                                                 $a                                     =                                     array                                     (4, 3, 2);                       
                                                 $n                                     =                                     count                                     (                                     $a                                     );                       
                                                 echo                                     cost(                                     $a                                     ,                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find minimum cost                       
                         // to reduce array size to 1,                       
           
                                                 // function to calculate the                       
                                                 // minimum cost                       
                                                 function                                     cost(a, n)                       
                                                 {                       
                                                 let min = a[0];                       
                                   
                                                 // find the minimum using                       
                                                 // for loop                       
                                                 for                                     (let i = 1; i< a.length; i++)                       
                                                 {                       
                                                 if                                     (a[i] < min)                       
                                                 min = a[i];                       
                                                 }                       
                                   
                                                 // Minimum cost is n-1 multiplied                       
                                                 // with minimum element.                       
                                                 return                                     (n - 1) * min;                       
                                                 }                       
           
                         // Driver code                       
                                   
                                                 let a = [ 4, 3, 2 ];                       
                                                 let n = a.length;                       
                                   
                                                 document.write(cost(a, n));                       
                                   
                         </script>                       

输出：

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

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

THE END

技术文章