购买所有硬币的最低成本，每枚硬币允许额外购买k枚硬币-yiteyi-C++库

你会收到一张N种不同面额硬币的清单。你可以支付相当于任何一枚硬币的金额，并可以获得该硬币。此外，一旦您支付了一枚硬币的费用，我们最多可以再选择K枚硬币，并且可以免费获得这些硬币。任务是找到获得给定K值的所有N个硬币所需的最小数量。

null

例如：

Input : coin[] = {100, 20, 50, 10, 2, 5},         k = 3Output : 7Input : coin[] = {1, 2, 5, 10, 20, 50},         k = 3Output : 3

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

根据这个问题，我们可以看到，花费1枚硬币，我们最多可以获得K+1枚硬币。因此，为了获得所有n枚硬币，我们将选择ceil（n/（k+1））硬币，如果我们选择最小的ceil（n/（k+1））（贪婪方法），那么选择硬币的成本将最小。最小的ceil（n/（k+1））硬币可以通过简单地按递增顺序对所有n值进行排序来找到。如果我们应该检查时间复杂度（n logn），则n表示排序元素，（k）表示添加总量。最后是时间复杂度：O（n logn）。

C++

                         // C++ program to acquire all n coins                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to calculate min cost                       
                         int                                     minCost(                                     int                                     coin[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // sort the coins value                       
                                                 sort(coin, coin + n);                       
           
                                                 // calculate no. of                       
                                                 // coins needed                       
                                                 int                                     coins_needed =                                     ceil                                     (1.0 * n /                       
                                                 (k + 1));                       
           
                                                 // calculate sum of                       
                                                 // all selected coins                       
                                                 int                                     ans = 0;                       
                                                 for                                     (                                     int                                     i = 0; i <= coins_needed - 1;                       
                                                 i++)                       
                                                 ans += coin[i];                       
                                   
                                                 return                                     ans;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     coin[] = {8, 5, 3, 10,                       
                                                 2, 1, 15, 25};                       
                                                 int                                     n =                                     sizeof                                     (coin) /                                     sizeof                                     (coin[0]);                       
                                                 int                                     k = 3;                       
                                                 cout << minCost(coin, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to acquire                       
                         // all n coins                       
                         import                                     java.util.Arrays;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // function to calculate min cost                       
                                                 static                                     int                                     minCost(                                     int                                     coin[],                       
                                                 int                                     n,                                     int                                     k)                       
                                                 {                       
                                   
                                                 // sort the coins value                       
                                                 Arrays.sort(coin);                       
           
                                                 // calculate no. of                       
                                                 // coins needed                       
                                                 int                                     coins_needed = (                                     int                                     )Math.ceil(                                     1.0                                     *                       
                                                 n / (k +                                     1                                     ));                       
           
                                                 // calculate sum of                       
                                                 // all selected coins                       
                                                 int                                     ans =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <= coins_needed -                                     1                                     ;                       
                                                 i++)                       
                                                 ans += coin[i];                       
           
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String arg[])                       
                                                 {                       
                                                 int                                     coin[] = {                                     8                                     ,                                     5                                     ,                                     3                                     ,                                     10                                     ,                       
                                                 2                                     ,                                     1                                     ,                                     15                                     ,                                     25                                     };                       
                                                 int                                     n = coin.length;                       
                                                 int                                     k =                                     3                                     ;                       
                                   
                                                 System.out.print(minCost(coin, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Anant Agarwal.                       

Python3

                         # Python3 program to                       
                         # acquire all n coins                       
           
                         import                                     math                       
           
                         # function to calculate min cost                       
                         def                                     minCost(coin, n, k):                       
           
                                                 # sort the coins value                       
                                                 coin.sort()                       
           
                                                 # calculate no. of                       
                                                 # coins needed                       
                                                 coins_needed                                     =                                     math.ceil(                                     1.0                                     *                                     n                                     /                                     /                       
                                                 (k                                     +                                     1                                     ));                       
           
                                                 # calculate sum of all                       
                                                 # selected coins                       
                                                 ans                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (coins_needed                                     -                                     1                                     +                                     1                                     ):                       
                                                 ans                                     +                                     =                                     coin[i]                       
                                   
                                                 return                                     ans                       
           
                         # Driver code                       
                         coin                                     =                                     [                                     8                                     ,                                     5                                     ,                                     3                                     ,                                     10                                     ,                       
                                                 2                                     ,                                     1                                     ,                                     15                                     ,                                     25                                     ]                       
                         n                                     =                                     len                                     (coin)                       
                         k                                     =                                     3                       
           
                         print                                     (minCost(coin, n, k))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to acquire all n coins                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // function to calculate min cost                       
                                                 static                                     int                                     minCost(                                     int                                     []coin,                       
                                                 int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 // sort the coins value                       
                                                 Array.Sort(coin);                       
           
                                                 // calculate no. of coins needed                       
                                                 int                                     coins_needed = (                                     int                                     )Math.Ceiling(1.0 *                       
                                                 n / (k + 1));                       
           
                                                 // calculate sum of                       
                                                 // all selected coins                       
                                                 int                                     ans = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i <= coins_needed - 1; i++)                       
                                                 ans += coin[i];                       
           
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []coin = {8, 5, 3, 10,                       
                                                 2, 1, 15, 25};                       
                                                 int                                     n = coin.Length;                       
                                                 int                                     k = 3;                       
                                   
                                                 // Function calling                       
                                                 Console.Write(minCost(coin, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program to acquire all n coins                       
           
                         // function to calculate min cost                       
                         function                                     minCost(                                     $coin                                     ,                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 // sort the coins value                       
                                                 sort(                                     $coin                                     ); sort(                                     $coin                                     ,                                     $n                                     );                       
           
                                                 // calculate no. of coins needed                       
                                                 $coins_needed                                     =                                     ceil                                     (1.0 *                                     $n                                     / (                                     $k                                     + 1));                       
           
                                                 // calculate sum of                       
                                                 // all selected coins                       
                                                 $ans                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <=                                     $coins_needed                                     - 1;                                     $i                                     ++)                       
                                                 $ans                                     +=                                     $coin                                     [                                     $i                                     ];                       
                                   
                                                 return                                     $ans                                     ;                       
                         }                       
           
                         // Driver Code                       
                         {                       
                                                 $coin                                     =                                     array                                     (8, 5, 3, 10,                       
                                                 2, 1, 15, 25);                       
                                                 $n                                     = sizeof(                                     $coin                                     ) / sizeof(                                     $coin                                     [0]);                       
                                                 $k                                     = 3;                       
                                                 echo                                     minCost(                                     $coin                                     ,                                     $n                                     ,                                     $k                                     );                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed                       
                         // by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to acquire all n coins                       
           
                         // Function to calculate min cost                       
                         function                                     minCost(coin, n, k)                       
                         {                       
                                   
                                                 // Sort the coins value                       
                                                 coin.sort(                                     function                                     (a, b){                                     return                                     a - b})                       
                                   
                                                 // Calculate no. of                       
                                                 // coins needed                       
                                                 var                                     coins_needed = Math.ceil(n /(k + 1));                       
           
                                                 // Calculate sum of                       
                                                 // all selected coins                       
                                                 var                                     ans = 0;                       
                                                 for                                     (                                     var                                     i = 0; i <= coins_needed - 1; i++)                       
                                                 ans += coin[i];                       
                                   
                                                 return                                     ans;                       
                         }                       
           
                         // Driver Code                       
                         var                                     coin = [ 8, 5, 3, 10,                       
                                                 2, 1, 15, 25 ]                       
                         var                                     n = coin.length;                       
                         var                                     k = 3;                       
           
                         document.write(minCost(coin, n, k));                       
           
                         // This code is contributed by noob2000                       
           
                         </script>                       

输出：

时间复杂度：O（n logn）

辅助空间：O（1）请注意，有更有效的方法可以找到给定数量的最小值。例如，方法6 m数组中最大（或最小）的元素可以在（n-m）logm+m logm）中找到第m个最小元素。

如何处理单个预定义数组的多个查询？ 在这种情况下，如果要求您为K的许多值找到上述答案，您必须快速计算，并且我们的时间复杂度会随着K的查询数量而增加。为了提供服务，我们可以在对所有N个值进行排序后维护前缀和数组，并且可以轻松快速地回答查询。认为

C++

                         // C++ program to acquire all                       
                         // n coins at minimum cost                       
                         // with multiple values of k.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Converts coin[] to prefix sum array                       
                         void                                     preprocess(                                     int                                     coin[],                                     int                                     n)                       
                         {                       
                                                 // sort the coins value                       
                                                 sort(coin, coin + n);                       
           
                                                 // Maintain prefix sum array                       
                                                 for                                     (                                     int                                     i = 1; i <= n - 1; i++)                       
                                                 coin[i] += coin[i - 1];                       
                         }                       
           
                         // Function to calculate min                       
                         // cost when we can get k extra                       
                         // coins after paying cost of one.                       
                         int                                     minCost(                                     int                                     coin[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // calculate no. of coins needed                       
                                                 int                                     coins_needed =                                     ceil                                     (1.0 * n / (k + 1));                       
           
                                                 // return sum of from prefix array                       
                                                 return                                     coin[coins_needed - 1];                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     coin[] = {8, 5, 3, 10,                       
                                                 2, 1, 15, 25};                       
                                                 int                                     n =                                     sizeof                                     (coin) /                                     sizeof                                     (coin[0]);                       
                                                 preprocess(coin, n);                       
                                                 int                                     k = 3;                       
                                                 cout << minCost(coin, n, k) << endl;                       
                                                 k = 7;                       
                                                 cout << minCost(coin, n, k) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // C# program to acquire all n coins at                       
                         // minimum cost with multiple values of k.                       
                         import                                     java .io.*;                       
                         import                                     java.util.Arrays;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 // Converts coin[] to prefix sum array                       
                                                 static                                     void                                     preprocess(                                     int                                     []coin,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // sort the coins value                       
                                                 Arrays.sort(coin);                       
                                   
                                                 // Maintain prefix sum array                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n -                                     1                                     ; i++)                       
                                                 coin[i] += coin[i -                                     1                                     ];                       
                                                 }                       
                                   
                                                 // Function to calculate min cost when we                       
                                                 // can get k extra coins after paying                       
                                                 // cost of one.                       
                                                 static                                     int                                     minCost(                                     int                                     []coin,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
                                   
                                                 // calculate no. of coins needed                       
                                                 int                                     coins_needed =(                                     int                                     ) Math.ceil(                                     1.0                       
                                                 * n / (k +                                     1                                     ));                       
                                   
                                                 // return sum of from prefix array                       
                                                 return                                     coin[coins_needed -                                     1                                     ];                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 static                                     public                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     []coin = {                                     8                                     ,                                     5                                     ,                                     3                                     ,                                     10                                     ,                                     2                                     ,                                     1                                     ,                                     15                                     ,                                     25                                     };                       
                                                 int                                     n = coin.length;                       
                                   
                                                 preprocess(coin, n);                       
                                   
                                                 int                                     k =                                     3                                     ;                       
                                                 System.out.println(minCost(coin, n, k));                       
                                   
                                                 k =                                     7                                     ;                       
                                                 System.out.println( minCost(coin, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python3 program to acquire all n coins at                       
                         # minimum cost with multiple values of k.                       
                         import                                     math as mt                       
           
                         # Converts coin[] to prefix sum array                       
                         def                                     preprocess(coin, n):                       
           
                                                 # sort the coins values                       
                                                 coin.sort()                       
                                   
                                                 # maintain prefix sum array                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 coin[i]                                     +                                     =                                     coin[i                                     -                                     1                                     ]                       
                                   
                         # Function to calculate min cost when we can                       
                         # get k extra coins after paying cost of one.                       
                         def                                     minCost(coin, n, k):                       
                                   
                                                 # calculate no. of coins needed                       
                                                 coins_needed                                     =                                     mt.ceil(                                     1.0                                     *                                     n                                     /                                     (k                                     +                                     1                                     ))                       
                                   
                                                 # return sum of from prefix array                       
                                                 return                                     coin[coins_needed                                     -                                     1                                     ]                       
                                   
                         # Driver code                       
                         coin                                     =                                     [                                     8                                     ,                                     5                                     ,                                     3                                     ,                                     10                                     ,                                     2                                     ,                                     1                                     ,                                     15                                     ,                                     25                                     ]                       
           
                         n                                     =                                     len                                     (coin)                       
           
                         preprocess(coin, n)                       
                         k                                     =                                     3                       
           
                         print                                     (minCost(coin, n, k))                       
           
                         k                                     =                                     7                       
           
                         print                                     (minCost(coin, n, k))                       
           
                         # This code is contributed                       
                         # by Mohit kumar 29                       

C#

                         // C# program to acquire all n coins at                       
                         // minimum cost with multiple values of k.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 // Converts coin[] to prefix sum array                       
                                                 static                                     void                                     preprocess(                                     int                                     []coin,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // sort the coins value                       
                                                 Array.Sort(coin);                       
                                   
                                                 // Maintain prefix sum array                       
                                                 for                                     (                                     int                                     i = 1; i <= n - 1; i++)                       
                                                 coin[i] += coin[i - 1];                       
                                                 }                       
                                   
                                                 // Function to calculate min cost when we                       
                                                 // can get k extra coins after paying                       
                                                 // cost of one.                       
                                                 static                                     int                                     minCost(                                     int                                     []coin,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
                                   
                                                 // calculate no. of coins needed                       
                                                 int                                     coins_needed =(                                     int                                     ) Math.Ceiling(1.0                       
                                                 * n / (k + 1));                       
                                   
                                                 // return sum of from prefix array                       
                                                 return                                     coin[coins_needed - 1];                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []coin = {8, 5, 3, 10, 2, 1, 15, 25};                       
                                                 int                                     n = coin.Length;                       
                                   
                                                 preprocess(coin, n);                       
                                   
                                                 int                                     k = 3;                       
                                                 Console.WriteLine(minCost(coin, n, k));                       
                                   
                                                 k = 7;                       
                                                 Console.WriteLine( minCost(coin, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to acquire all n coins at                       
                         // minimum cost with multiple values of k.                       
           
                         // Converts coin[] to prefix sum array                       
                         function                                     preprocess(&                                     $coin                                     ,                                     $n                                     )                       
                         {                       
                                                 // sort the coins value                       
                                                 sort(                                     $coin                                     );                       
           
                                                 // Maintain prefix sum array                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     - 1;                                     $i                                     ++)                       
                                                 $coin                                     [                                     $i                                     ] +=                                     $coin                                     [                                     $i                                     - 1];                       
                         }                       
           
                         // Function to calculate min cost                       
                         // when we can get k extra coins                       
                         // after paying cost of one.                       
                         function                                     minCost(&                                     $coin                                     ,                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 // calculate no. of coins needed                       
                                                 $coins_needed                                     =                                     ceil                                     (1.0 *                                     $n                                     / (                                     $k                                     + 1));                       
           
                                                 // return sum of from prefix array                       
                                                 return                                     $coin                                     [                                     $coins_needed                                     - 1];                       
                         }                       
           
                         // Driver Code                       
                         $coin                                     =                                     array                                     (8, 5, 3, 10,                       
                                                 2, 1, 15, 25);                       
                         $n                                     = sizeof(                                     $coin                                     );                       
                         preprocess(                                     $coin                                     ,                                     $n                                     );                       
           
                         $k                                     = 3;                       
                         echo                                     minCost(                                     $coin                                     ,                                     $n                                     ,                                     $k                                     ) .                                     ""                                     ;                       
           
                         $k                                     = 7;                       
                         echo                                     minCost(                                     $coin                                     ,                                     $n                                     ,                                     $k                                     ) .                                     ""                                     ;                       
           
                         // This code is contributed by ita_c                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to acquire all n coins at                       
                         // minimum cost with multiple values of k.                       
                                   
                                                 // Converts coin[] to prefix sum array                       
                                                 function                                     preprocess(coin,n)                       
                                                 {                       
                                                 // sort the coins value                       
                                                 coin.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                   
                                   
                                                 // Maintain prefix sum array                       
                                                 for                                     (let i = 1; i <= n - 1; i++)                       
                                                 coin[i] += coin[i - 1];                       
                                                 }                       
                                   
                                                 // Function to calculate min cost when we                       
                                                 // can get k extra coins after paying                       
                                                 // cost of one.                       
                                                 function                                     minCost(coin,n,k)                       
                                                 {                       
                                                 // calculate no. of coins needed                       
                                                 let coins_needed =Math.ceil(1.0                       
                                                 * n / (k + 1));                       
                                   
                                                 // return sum of from prefix array                       
                                                 return                                     coin[coins_needed - 1];                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 let coin=[8, 5, 3, 10, 2, 1, 15, 25];                       
                                                 let n = coin.length;                       
                                                 preprocess(coin, n);                       
                                                 let k = 3;                       
                                                 document.write(minCost(coin, n, k)+                                     "<br>"                                     );                       
                                   
                                                 k = 7;                       
                                                 document.write( minCost(coin, n, k));                       
                                   
                                                 // This code is contributed by rag2127                       
                                   
                         </script>                       

输出：

时间复杂度：O（n logn）

辅助空间：O（1）预处理后，k的每个查询都需要O（1）个时间。本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章