Problem:

Given T number, you have to select N numbers such that Max(Selection)-Min(Selection) is minimum. Print Max(Selection)-Min(Selection)

ex: if T=3 and N=2 and numbers are 1,2,4 , then selection can be (1,2) or(2,4) or (1,4).

max(1,2)-min(1,2)=2-1=1

max(2,4)-min(2,4)=4-2=2

max(1,4)-min(1,4)=4-1=3

Clearly 1 is minimum, so output should be 1.

ex: if T=3 and N=2 and numbers are 1,2,4 , then selection can be (1,2) or(2,4) or (1,4).

max(1,2)-min(1,2)=2-1=1

max(2,4)-min(2,4)=4-2=2

max(1,4)-min(1,4)=4-1=3

Clearly 1 is minimum, so output should be 1.

**Input Format:**

Total number T

Subset number N

next T lines having numbers

Subset number N

next T lines having numbers

**Output Format:**

Max(Selection)-Min(Selection)

**Constraints:**

none

Sample Input

7

3

2

6

10

12

4

11

16

3

2

6

10

12

4

11

16

Sample Output:

2

2

Explanations:

We have to select 3 numbers from 7 numbers- 2,6,10,12,4,11,16.

We should select 10,11,12. Max(10,11,12)=12. Min(10,11,12)=10. Diff=2. All other possible combinations have difference more than 2.

We have to select 3 numbers from 7 numbers- 2,6,10,12,4,11,16.

We should select 10,11,12. Max(10,11,12)=12. Min(10,11,12)=10. Diff=2. All other possible combinations have difference more than 2.

Solution:

chomp($n=<STDIN>);

for($i=0;$i<$t;$i++)

{

chomp($tmp=<STDIN>);

push(@arr,$tmp);

}

@arr=sort{$a<=>$b}@arr;

$ans=$arr[$t-1];

$up=$t-$n;

for($i=0;$i<=$up;$i++)

{

$t=$arr[$i+$n-1]-$arr[$i];

if($t<$ans){$ans=$t;}

}

print $ans;

Tips:

Sort all numbers and then calculate for all possible orders using sorted list

## No comments:

## Post a Comment