MINMAX 1

QUESTION

Given a list of N integers, your task is to select K integers from the list such that its unfairness is minimized.\nif (x1,x2,x3,,xk) are K numbers selected from the list N, the unfairness is defined as max(x1,x2,,xk)-min(x1,x2,,xk)\nwhere max denotes the largest integer among the elements of K, and min denotes the smallest integer among the elements of K.\n\nInput Format\nThe first line contains an integer N.\nThe second line contains an integer K.\nN lines follow. Each line contains an integer that belongs to the list N.\n\nNote: Integers in the list N may not be unique.\n\nOutput Format\nAn integer that denotes the minimum possible value of unfairness.\n\nConstraints\n2<=N<=10^5\n2<=K<=N\n0=<integer in N <=10^9.

ANSWER

#include <iostream>
//#include <cmath>
//#include <cstdio>
//#include <vector>

//#include <algorithm>
//#include <climits>
using namespace std;

void merge(unsigned long long int a[],int l, int p,int h)
{
       int j,i,t,x,y,k;    
       x = l;
       y = p+1;
       k = 0;
       unsigned long long int b[h-l+1];
       for(i=l;i<=h;i++)
       {
              if(x>p)
              {
                     b[k] = a[y];
                     k++;
                     y++;
              }
              else if(y>h)
              {
                     b[k] = a[x];
                     k++;
                     x++;
              }
              else if(a[x]<a[y])
              {
                     b[k] = a[x];
                     x++;
                     k++;
              }
              else
              {
                     b[k] = a[y];
                     y++;
                     k++;
              }
       }
       for(i=0;i<k;i++)
       {
              a[l] = b[i];
              l++;
       }
       return;
}

void sort(unsigned long long int a[],int l,int h)
{
       if(l<h)
       {
              int p = (l+h)/2;
              //printf("%d ",p);
              sort(a,l,p);
              sort(a,p+1,h);
             
              merge(a,l,p,h);
       }
       return;
}

int main()
{
    int N,K;
    cin >> N >> K;
    unsigned long long int a[N],d,min=100000000000,i;
    for (int i=0; i<N; i++)
    {
       cin>>a[i];
    }
    sort(a,0,N-1);
       for(i=0;i<=N-K;i++)
    {
       d = a[K+i-1] - a[i];
       if(d<min)
       {
              min = d;
       }
    }
    cout<<min<<endl;
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro