Minimize cost to split an array into K subsets such that the cost of each element is its product with its position in the subset | C ++ program to implement the above approach ; Function to find the minimum cost to split array into K subsets ; Sort the array in descending order ; Stores minimum cost to split the array into K subsets ; Stores position of elements of a subset ; Iterate over the range [ 1 , N ] ; Calculate the cost to select X - th element of every subset ; Update min_cost ; Update X ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMinCost ( int * arr , int n , int k ) { sort ( arr , arr + n , greater < int > ( ) ) ; int min_cost = 0 ; int X = 0 ; for ( int i = 0 ; i < n ; i += k ) { for ( int j = i ; j < i + k && j < n ; j ++ ) { min_cost += arr [ j ] * ( X + 1 ) ; } X ++ ; } return min_cost ; } int main ( ) { int arr [ ] = { 9 , 20 , 7 , 8 } ; int K = 2 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << getMinCost ( arr , N , K ) << endl ; }