angry.cpp

/*Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and 
would like to distribute one packet to each of the K children in the village (each packet may contain 
different number of candies). To avoid a fight between the children, he would like to pick K out of N packets 
such that the unfairness is minimized.

Suppose the K packets have (x1, x2, x3,….xk) candies in them, where xi denotes the number of candies in the 
ith packet, then we define unfairness as

Sum [abs(X(i) - X(j))]    1<=i<j<=N

where |a| denotes the absolute value of a.

Input Format
The first line contains an integer N.
The second line contains an integer K. N lines follow each integer containing the candy in the ith packet.

Output Format
A single integer which will be minimum unfairness.

Constraints
2<=N<=10^5
2<=K<=N 
0<= number of candies in each packet <=10^9

Sample Input #00

7
3
10
100
300
200
1000
20
30

Sample Output #00
40

Explanation #00

Bill Gates will choose packets having 10, 20 and 30 candies.So unfairness will be |10-20| + |20-30| + |30-10| = 40. 
It will be minimum as compared to any other distribution which can be verified .

Sample Input #01

10
4
1
2
3
4
10
20
30
40
100
200
Sample Output #01

10
Explanation #01

Bill Gates will choose 4 packets having 1,2,3 and 4 candies. So, unfairness will be |1-2| + |1-3| + |1-4| + |2-3| + 
|2-4| + |3-4| = 10

*/
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	long int *a;
	long int i,n,k,j,diff1,diff2,l;
        long long int diff,min = 9223372036854775807;
	//cout<<"enter no of elements: ";
	cin>>n>>k;
	a = new long int[n];
	for(i = 0;i<n;i++)
		cin>>a[i];
	std::sort(a,a+n);
//	for(int i = 0;i < n;i++)
  //      cout<<a[i]<<endl;
	    
	
        if(n == k)
        {
        	diff = 0;
        	for(i = n - 1; i >= 0; i--)
        	{
            		diff = diff + (long long int) (a[i] * i - a[i] * (n -i -1));
        	}
        	min = diff;
    	}
        else
    	{
		for(i = 0 ;i < n - k + 1;i++)
		{
			diff = 0;
			l = 0;
			for(j = i;j < i + k;j++)
			{
				diff = diff + (long long int) (a[j] * l - a[j] *(k-l-1));
				if(min <= diff)
					break;
				l++;
			}
			if(j == i + k && diff >= 0)
				min = diff;
			
		}
    	}
 
	cout<<min<<endl;
	delete[] a;
	return 0;
}

@sagarverma: I tried using unsigned long long. But in vain. Infact it is now working for just 2 to 3 cases.

I think you should not use merge sort...things like left[i] = 1000000000;
right[j] = 1000000000; might be creating problems

@nerdguy06: I am using std::sort now. Passes 8 cases out 16 cases. For rest of the 7, says wrong answer. Is something wrong with my algorithm?

that code aint working!!!

heres the working code...
credit: k_maro codes
sanjay kumar, arvind p.bright, akil sai

include

using namespace std;

include<stdio.h>

void input(int a[],int n)
{
for(int i=0;i<n;i++)
{cin>>a[i];
}

}

void answer(int a[], int k,int n)
{ int temp;
for( int i=0;i<n;i++)
{for( int j=0;j<n-1;j++)
{if(a[j]>a[j+1])
{temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}

cout<<endl;
cout<<endl;int b[n];
for(int i=0;i<n;i++)
    b[i]=a[i];


for( int i=0;i<n;i++)
    {cout<<"\n"<<b[i];
    }


int min=32000;
for(int i=0;i<n-k+1;i++)
    {if(min>((b[k+i-1])-(b[i])))
        min=b[k+i-1]-b[i];
    }

cout<<"\n"<<min;
}

int main()
{
int n,k;
int a[n];
cin>>n>>k;
input(a,n);
answer(a,k,n);
return 0;
}

@vidyavnv I've asked a question regarding this and got a couple of algorithms. Maybe they can help you too:

http://stackoverflow.com/questions/19482332/find-subset-with-k-elements-that-are-closest-to-eachother

@gnima: I can't understand the python code. What is the algorithm?