Count Inversions
PHP
Hard
6 views
Problem Description
Count pairs i a[j].
Input Format
First n. Next line n integers.
Output Format
One integer inversions.
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$idx=0; $n=intval($tokens[$idx++] ?? 0);
$a=[];
for($i=0;$i<$n;$i++) $a[] = intval($tokens[$idx++] ?? 0);
function sortCount($arr,&$inv){
$n=count($arr);
if($n<=1) return $arr;
$mid=intdiv($n,2);
$left=array_slice($arr,0,$mid);
$right=array_slice($arr,$mid);
$left=sortCount($left,$inv);
$right=sortCount($right,$inv);
$i=0; $j=0; $output=[];
while($i<count($left) && $j<count($right)){
if($left[$i] <= $right[$j]) $output[]=$left[$i++];
else{ $output[]=$right[$j++]; $inv += (count($left)-$i); }
}
while($i<count($left)) $output[]=$left[$i++];
while($j<count($right)) $output[]=$right[$j++];
return $output;
}
$inv=0;
sortCount($a,$inv);
echo strval($inv);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!