Problem:

There are n rats and n holes in a straight line. Each hole can accommodate only 1 rat. A rat may move to its right or left. To move 1 block, he needs 1 minute. Find minimum time required for all rats to occupy a hole from their current position.

**Input Format:**

Line2: position of holes separated by space

**Output Format:**

minimum time required

**Constraints:**

none

Sample Input

1 2 7

0 8 9

0 8 9

Sample Output:

6

6

Explanations:-

Rat and hole initial positions: O R R _ _ _ _ R O O

So rat 1 will move 1 position left, rat 2 will move 6 position right and rat 3 will move 2 position right, so minimum time for all rats to occupy holes is 6

So rat 1 will move 1 position left, rat 2 will move 6 position right and rat 3 will move 2 position right, so minimum time for all rats to occupy holes is 6

Solution:

@arrm=split(" ",$mouse);

chomp($holes=<STDIN>);

@arrh=split(" ",$holes);

@arrh1=sort{$a<=>$b}@arrh;

@min=();

@h=();

@arrm1=sort{$a<=>$b}@arrm;

$c=0;

for($m=0;$m<$n;$m++)

{

if($arrm1[$m] == $arrh1[$m])

{

$c++;

}

}

$diff=0;

$n1=$n;

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

$k=0;

foreach(@arrm1)

{

if($c == $n)

{

push(@min,$diff);

}

$diff1 = $_ - $arrh1[$k];

$k++;

if($diff1<0)

{

$diff1 = $diff1 * -1;

}

push(@min,$diff1);

}

@ans=sort{$a<=>$b}@min;

print "$ans[$n-1]";

Tips:

Sort holes and rat positions and max(h(i)-r(i)) is the answer

## No comments:

## Post a Comment