Chocolate Distribution Problem

-
/*
Given an array of n integers where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are m students, the task is to distribute chocolate packets such that:
  1. Each student gets one packet.
  2. The difference between the number of chocolates in packet with maximum chocolates and packet with minimum chocolates given to the students is minimum.
Examples:
Input : arr[] = {7, 3, 2, 4, 9, 12, 56}
m = 3
Output: Minimum Difference is 2
We have seven packets of chocolates and
we need to pick three packets for 3 students
If we pick 2, 3 and 4, we get the minimum
difference between maximum and minimum packet
sizes.
Input : arr[] = {3, 4, 1, 9, 56, 7, 9, 12}
m = 5
Output: Minimum Difference is 6
The set goes like 3,4,7,9,9 and the output
is 9-3 = 6
Input : arr[] = {12, 4, 7, 9, 2, 23, 25, 41,
30, 40, 28, 42, 30, 44, 48,
43, 50}
m = 7
Output: Minimum Difference is 10
We need to pick 7 packets. We pick 40, 41,
42, 44, 48, 43 and 50 to minimize difference
between maximum and minimum.


*/


// ans were correct but got TLE error
// when used mergesort got answer
// idea is sort the array and at every window size last element, first element will be the max and min //of the particular window so, we get the min difference

#include<iostream>
using namespace std;
void swap(int *x, int *y)
{
    int p;
    p=*x;
    *x=*y;
    *y=p;
}
int main()
 {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
this breaks the contact of c from c++, now c++ win only execute c++ functions making the c++ program run faster by 5-10%.
*/
   
     int t,n,m,minidx,j,i;
     cin>>t;
    while(t--)
{
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
     
    }
    cin>>m;
 
    // now sorting it -- selection sort
    // i.e min first so last element will be auto sorted so till <n-1 outerloop
    // inner loop will be from i+1 to n coz we select i first then compare ith with i+1 to n
    // and swamp min with ith position
    for(i=0;i<n-1;i++)
    {
        minidx=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[minidx])
            {
                minidx=j;
            }
        }
        swap(&a[i],&a[minidx]);
     
    }
   //  for(i=0;i<n;i++)
   // {
   //     cout<<a[i];
     
   // }
    //sorted
 
    // now what we have to do is find ( diff bw max and min ) in every window of size m
    // the min of sizes is ans
    //  m-1 is the last element of array of size m
    int min =a[m-1]-a[0];
    //cout<<min<<" ";
    for(i=0;i<=n-m;i++)
    {
        int mm=a[m-1+i]-a[i];
        //cout<<mm<<" ";
            if(mm<min )
            {
                min=mm;
            }
         
        }
        cout<<min<<endl;

 
}
return 0;
}

Comments

Post a Comment

Popular posts from this blog

-
// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach // C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std;   int SieveOfAtkin(int limit) {     // 2 and 3 are known to be prime     if (limit > 2)         cout << 2 << " ";     if (limit > 3)         cout << 3 << " ";       // Initialise the sieve array with false values     bool sieve[limit];     for (int i = 0; i < limit; i++)         sieve[i] = false;     for (int x = 1; x * x < limit; x++) {         for (int y = 1; y * y < limit; y++) {                           // Main part of Sieve of Atkin             int n = (4 * x * x) + (y * y);             if (n <= limit && (n % 12 == 1 || n % 12 == 5))                 sieve[n] ^= true;               n = (3 * x * x) + (y * y);             if (n <= limit &
Read more

Linked List 10 operations from which problems are made ( complete guide for you)

-
/* These are the functions we will implement make your seatbelts tight and start progrmming cout<<" 1. Insert node at begining"<<endl; cout<<" 2. Append a node"<<endl; cout<<" 3. display the l.l"<<endl; cout<<" 4. Insert before a selected node"<<endl; cout<<" 5. Insert after a selected node "<<endl; cout<<" 6.Delete a particular node"<<endl; cout<<" 7.Reverse A L.L "<<endl; cout<<" 8. Do bot reverse the l.l but display the reversed order (using recursion)"<<endl; cout<<"9. find middle element in a list using slow and fast pointer"<<endl; cout<<"10. check if linked list is palindrome or not (we know if even f=NULL odd f->next=NULL)"<<endl; cout<<" 11. exit"<<endl; */ #include<iostream> using namespace std; struct node{
Read more

Stack - print bracket number

-
/ * example 2 (0+1)*0(0+1)*0(0+1)* (1*0)*1* o/p 1 1 2 2 3 3  1 1  Example: Input: 3 (a+(b*c))+(d/e) ((())(())) ((((() Output: 1 2 2 1 3 3 1 2 3 3 2 4 5 5 4 1 1 2 3 4 5 5 */ #include<bits/stdc++.h> using namespace std; int main()  { int t; cin>>t; while(t--) {     string s;     stack <int> st;     int c=0; // we maintain the count of open brackets     cin>>s;     for(int i=0;i<s.length();i++)     {         if(s[i]=='(')         {c++;         cout<<c<<" ";         st.push(c);         }         if(s[i]==')')         {             cout<<st.top()<<" ";             st.pop();         }     }     cout<<endl; } return 0; }
Read more