-
Notifications
You must be signed in to change notification settings - Fork 0
/
lilys-homework.php
57 lines (41 loc) · 1.23 KB
/
lilys-homework.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<?php
/*
* Complete the 'lilysHomework' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
function swapCount($array, $heap, $dic) {
$swapCount = 0;
for ($x = 0, $l = count($array); $x < $l; $x++) {
$expected = $heap->extract();
$found = $array[$x];
if ($expected != $found) {
$place = $dic[$expected];
$array[$x] = $expected;
$array[$place] = $found;
$dic[$expected] = $x;
$dic[$found] = $place;
$swapCount++;
}
}
return $swapCount;
}
function lilysHomework($arr) {
$maxHeap = new SplMaxHeap();
$minHeap = new SplMinHeap();
$dic = [];
foreach ($arr as $key => $value) {
$maxHeap->insert($value);
$minHeap->insert($value);
$dic[$value] = $key;
}
return min(swapCount($arr, $minHeap, $dic), swapCount($arr, $maxHeap, $dic));
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$n = intval(trim(fgets(STDIN)));
$arr_temp = rtrim(fgets(STDIN));
$arr = array_map('intval', preg_split('/ /', $arr_temp, -1, PREG_SPLIT_NO_EMPTY));
$result = lilysHomework($arr);
fwrite($fptr, $result . "\n");
fclose($fptr);