輸入:數組,所有值為非負整數
目標:通過變換使數組的每個值為所有值的平均值,並且迭代次數最少
變換方法:某個值自身減一,使其緊鄰左邊或緊鄰右邊的值加一。數組第一個值只能向右傳遞1,最後一個向左傳遞1. 變換過程中數組內所有值不可為負。
例1:
輸入 : [0, 3, 3]
第一次: [1, 2, 3] [1, 3, 2]
第二次: [2, 2, 2]
例2
[2, 4, 6, 2, 1]
[3, 3, 5, 2, 2]
[3, 3, 4, 2, 3]
[3, 3, 3, 3, 3]
例3
[1, 0, 7, 0]
[1, 1, 6, 0]
[2, 1, 5, 0]
[2, 2, 4, 0]
[2, 2, 3, 1]
[2, 2, 2, 2]
這個問題有什麼好的算法解決嗎,例子不是唯一解。求思路,用php實現。
$ar = [0, 3, 3];
$ar = [2, 4, 6, 2, 1];
$ar = [1, 0, 7, 0];
$ar = [5, 5, 5, 5, 25];
do {
$loop = 0;
for($i=0; $i<count($ar) - 1; $i++) {
if($n = casecmp($ar[$i], $ar[$i+1])) {
$ar[$i] += $n;
$ar[$i+1] -= $n;
$loop++;
}
}
printf("[%s]\n", join(', ', $ar));
}while($loop);
function casecmp($a, $b) {
if($a == $b) return 0;
return $a > $b ? -1 : 1;
}