CareerCup

sort the array ..take a minimum priority queue ..insert first m packets and later on add the coming (n-m) packets to the first element of priority queue.

We can use Binary Search (Divide & Conquer) for the solution:

#include <bits/stdc++.h>
using namespace std;

bool is_possible(int A[], int size, int B, int curr_min) {
    int students = 1, sum = 0;
    
    for (int i = 0; i < size; i++) {
        if (A[i] > curr_min)
            return false;
        if (sum + A[i] > curr_min) {
            students++;
            sum = A[i]; 
            if (students > B)
                return false;
        }
        else
            sum = sum + A[i];
    }
    return true;
}

int toffees(int A[], int size, int B) {
    long long sum = 0;
    
    if(size < B)
        return -1;
 
    for(int i = 0; i < size; i++)
        sum = sum + A[i];
        
    long long start = 0, mid = 0, end = sum;
    int result = INT_MAX;
    
    while(start <= end) {
        mid = (start + end) / 2;
        if (is_possible(A, size, B, mid)) {
            result = min(result, (int)mid);
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    return result;
}

int main() {
	int A[] = {12, 34, 67, 90};
    	int size = sizeof(A) / sizeof(A[0]);
	cout << toffees(A, size, 2);
	return 0;
}

a. Sort c1, c2, c3 ... cn, descending order

b. Create array of size [M]

c. Loop over numbers
Store first M numbers in the array. ( first col will have the highest number )

d. int highestColumn = 0 ( since col 0 has the highest value )

e. Loop over columns in the array, from last to first i.e. in ascending order.
This is to ensure the lowest digit is added the next highest number, thus creating the lowest combo.
&&
Loop until c series numbers finish

if ( array[highestColumn] >= array[currentColumn] + c )
Add c in current column
else
Add c in current column
highestColumn = currentColumn

Print value of array[highestColumn]

@deep.kulshreshtha, Can you share bit more insight about your solution, and one more thing, question says that we can only choose consecutive toffee packets then sorting will disturb the order. Isn't it?

Number of boxes, M range from [1,N].
When M = 1, only one ordering is possible, i.e all toffee packets in one box => ans will be sum of all toffees -> call this is the upper bound
Similarly, when M = N, again only one ordering is possible, i.e each toffee packet in each of the M boxes => ans will max of the toffees -> call this is the lower bound

So, we can binary search in the range(lower bound to upper bound).
Find mid = (upper-lower)/2
Now, check if mid is possible by putting toffee packets in <= m boxes.
If it is possible, check for a lower half.
Else, check for the higher half.

sort the n packets in descending order according to ci.
take a min priority queue and push the first m packets in the queue
now for remaining n-m packet pop out the first element from min priority queue add ci corresponding to current packet,push the result in priority queue.
at last the largest element can be found easily from the queue.

#include<bits/stdc++.h>
#define ll long long
using namespace std;



int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int N,M;
        cin>>N>>M;
        int A[N];
        priority_queue<int,vector<int>,greater<int> > Q;
        for(int i=0;i<N;i++)
        {
            cin>>A[i];
        }
        sort(A,A+N);
        int i;
        for(i=0;i<M;i++)
           Q.push(A[i]);
           int temp=N-M;
           int index=N-1;
        while(temp--)
        {
            //cout<<Q.top()<<endl;
            int data=Q.top()+A[index--];
            Q.pop();
            Q.push(data);
        }
        int res;
        while(!Q.empty())
        {
            res=Q.top();
           // cout<<Q.top()<<endl;
            Q.pop();
        }
        cout<<res<<endl;
    }
   return 0;
}