Angry Children
Problem Statement
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 any fighting among the children, he would like to pick K out of N packets, such that 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
max(x1,x2,...xk) - min(x1,x2,...xk)
where max denotes the highest value amongst the elements, and min denotes the least value amongst the elements. Can you figure out the minimum unfairness and print it?
Input Format
The first line contains an integer N. The second line contains an integer K. N lines follow. Each line contains an integer that denotes the candy in the ith packet.
Output Format
An integer that denotes the minimum possible value of unfairness.
Constraints
1<=N<=105 1<=K<=N 0<= number of candies in any packet <=109
Sample Input #00
7
3
10
100
300
200
1000
20
30
Sample Output #00
20
Explanation #00
Here K = 3. We can choose packets that contain 10,20,30 candies. The unfairness is
- max(10,20,30) - min(10,20,30) = 30 - 10 = 20
Sample Input #01
10
4
1
2
3
4
10
20
30
40
100
200
Sample Output #01
3
Explanation #01
Here K = 4. We can choose the packets that contain 1,2,3,4 candies. The unfairness is
- max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3
Soluzione di Eddy
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100000
#define MAX_VAL 1000000001
int candies[MAX];
void MergeSort (int *candies, int primo, int ultimo);
void Merge (int *candies, int primo, int ultimo, int mezzo);
int Unfairness (int *candies, int len, int k);
int main() {
int N,K;
int i;
FILE *fin;
if ((fin=fopen("input.txt","r")) == NULL)
exit(2);
fscanf(fin,"%d %d",&N,&K);
for(i = 0;i < N;i++)
fscanf(fin,"%d",candies + i);
MergeSort (candies, 0, N-1);
int unfairness = Unfairness (candies, N, K-1);
printf("%d\n",unfairness);
return 0;
}
/* IDEA:
* siccome l'array e` ordinato max = i-esima pos + (k-1), min = i-esima pos,
* mi basta scorrere l'array pagando O(n), ma avevo ordinato: O(nlog(n))
*/
int Unfairness (int *candies, int len, int k)
{
int i, min, tmp;
i=0; min=candies[len-1];
while (i+k < len){
tmp = candies[i+k] - candies[i];
if (tmp < min) min = tmp;
i++;
}
return min;
}
void MergeSort (int *candies, int primo, int ultimo)
{
if (primo < ultimo){
int mezzo = (primo+ultimo)/2;
MergeSort(candies, primo, mezzo);
MergeSort(candies, mezzo+1, ultimo);
Merge(candies, primo, ultimo, mezzo);
}
}
void Merge (int *candies, int primo, int ultimo, int mezzo)
{
int i, j, k, h;
int tmp[MAX];
i = primo; j = mezzo+1; k = primo;
/* "compongo tmp" fino a quando non esaurisco una meta` */
while (i <= mezzo && j <= ultimo){
if (candies[i]<=candies[j])
tmp[k++] = candies[i++];
else
tmp[k++]=candies[j++];
}
j=ultimo;
/* se sono rimasti degli elementi nella prima meta` saranno i maggiori */
for (h=mezzo; h>=i; h--)
candies[j--]=candies[h];
for (j=primo; j<=k-1; j++)
candies[j]=tmp[j];
}