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;
}

@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?