Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
Medium
Problem Statement (Simplified):
For given values of N and K, an array of N elements is given. You can pick at most K items in one turn, each turn costs you (turn number * element value). For all values i between 1 and N, calculate the minimum possible value of picking exactly i items.
Test Case
Input:
1
5 2
4 5 3 7 5
Output:
3 7 15 24 39
Explanation:
For K=4,
We can select 3, 4, 5, and 5. As our daily limit is 2, so we split chocolates in 2 days, we'll select larger chocolates for day 1 and select rest for day 2. So we can select chocolates like:
1st Day = 5 and 5
2nd Day = 3 and 4
So, its cost will be 1(5)+1(5)+2(3)+2(4), so our final cost becomes 24. Hence, for K=4 we print 24.See original problem statement here
Solving Approach :
1) If we sort the provided array, it would be easy to pick items, as we can pick elements from the start of the array and the total cost would be minimal.
2) We can use Cummulative Array to solve this problem.
Cummulative Array: Cummulative Array is an array that contains the sum of all elements before the current index and element at the current index.
3) For any value between K, the minimum cost will be the sum of the current index. But if maximum capacity i.e.Mreaches or is crossed, it also includes cost at (current day – capacity)th day.
Examples
Let array
Abe,Graphic-1 Here
sizeof array is5and we have capacity of2.We arrange array in non-decreasing order. So array
Abecomes,Graphic-2 Here
We create a cummulative array from our array
A, hence our arrayAbecomes,Graphic-3 Here
For any value between
1andsize, for e.g.4, it will represent index3in our array, as value is greater than our capacity, so minimum cost will be,minimumCost = currentDayCost + (currentDay – capacity)th Day cost
minimumCost = 18 + (4-3)th day cost
minimumCost = 18 + A[1]
minimumCost = 18 + 7
minimumCost = 25,Hence,
minimumCostwill be25for the index3, hence we get values for all days like this.
Solutions
#include <stdio.h>
void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1];
long long right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
int n, k;
scanf("%d%d",&n,&k);
long long int chocolate[n];
for(int i=0; i<n; i++)
scanf("%lld",&chocolate[i]);
mergeSort(chocolate, 0, n-1);
for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];
for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
printf("%lld ",chocolate[i]);
}
printf("\n");
}
}
#include <bits/stdc++.h>
using namespace std;
void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1]={0};
long long right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
cin>>test;
while(test--){
int n, k;
cin>>n>>k;
long long int chocolate[n];
for(int i=0; i<n; i++)
cin>>chocolate[i];
mergeSort(chocolate, 0, n-1);
for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];
for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
cout<<chocolate[i]<<" ";
}
cout<<endl;
}
}
import java.util.*;
import java.io.*;
public class Main {
static void merge(long arr[], int start, int mid, int end){
long left[] = new long[mid-start+1];
long right[] = new long[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
static void mergeSort(long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
public static void main(String args[]) throws IOException {
InputStreamReader r = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(r);
int test = Integer.parseInt(br.readLine());
while(test-->0){
String s= br.readLine();
String[] s1 = s.split(" ");
int n = Integer.parseInt(s1[0]);
int k = Integer.parseInt(s1[1]);
long chocolate[] = new long[n];
s = br.readLine();
String s2[] = s.split(" ");
for(int i=0; i<n; i++)
chocolate[i] = Long.parseLong(s2[i]);
mergeSort(chocolate, 0, n-1);
for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];
for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
System.out.print(chocolate[i]+" ");
}
System.out.println();
}
br.close();
}
}
Space Complexity: O(
1)
[forminator_quiz id="1207"]
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.