我需要一个提示来开始解决这个编程难题

           (0)
     -------------      
     |           | 
    (2)         (1)
 ---------    -------   
 |       |    |     |
[3p]     ..   ..   (3)
                  ------
                  |     |
                 ...    ..

您的逻辑应该在内存中创建此树，每个节点包含以下数据结构。

BalanceIdx: Integer;    //The balance index number if any. -1 indicates none
InitialPounds: Integer; //Initial weight in the node 
AddedPounds: Integer;   //The weight you added when processing. Default is 0
TotalWeight: Integer;   //**Total weight of a node including all its children. This is also our indication that a particular branch is already traversed. Default is -1

我们正在讨论一个递归函数，它基本上知道它在树的任何节点上只有两条路径或没有路径可走。每个递归都被认为是坐在一个天平盘上。

逻辑如下。

1. 从根节点开始，直到找到一个没有路径的节点。

2. 利用InitialPounds更新TotalWeight

3. 现在看看节点的其他兄弟是否有它的TotalWeight设置。如果NO，设置递归函数的根目录并执行。

4. 如果是，计算差值并更新您所在位置的AddedPounds。现在转到父节点并更新它的TotalWeight。(别忘了在余额上加10便士。)然后进入父级，重复3。

一旦递归函数完成了对整个树的遍历，您将在每个节点中记录AddedPounds。使用另一个递归函数来构造输出。

剧透警告:包含完整的解决方案(除了读取输入)

这个问题相当老了，看起来很有趣，所以我只是去解决它(在C中，而不是像这样标记的PHP)，在几个提示式的开头段落之后。我使用了冗长的变量名和注释，所以它应该作为伪代码工作。我是要写类似c的伪代码，但从来没有碰到任何值得总结的东西。

由于输入格式将数字分配给所有余额，因此最简单的方法是将这些索引用于结构体数组。如果您可以假设余额小于2^31，则可以通过使用32位整型而不是64位指针来节省内存。(负索引是空的哨兵，就像基于指针的树/列表实现中的NULL指针)

struct balance {
    // weights sitting directly on the pans of this balance
    float weight_left, weight_right;  // or unsigned int; the question only said the balance-count was an int.  I assumed the balance-IDs were int, too
    // optionally: float adjustment;  // For recording our changes.  negative or positive for adding to left or right balance.
    // references to other balances: negative means empty-list, otherwise index into an array.
    int next;           // linked-list of sibling balances on the same pan of a parent
    int left, right;    // list-heads for balances on the left and right pan
};

当他们说你应该把重量加到"最低"平衡时，我猜他们的意思是根在底部。它不是一棵挂着天平的树。

您可以在已经带有余额的余额上添加重量。所以给树叶子上的空锅增加重量并不复杂。(这需要以一种保持每个子树单独平衡的方式划分权重)。

这看起来很容易递归求解。

• 子树可以自己平衡，不需要任何关于其他平衡的信息。
• 重量和其他平衡的组合构成了左右平底锅的负载并不重要。你只需要这两个总数。通过直接向较轻的锅中添加重量来平衡。
• 在平衡其所有子树之后平衡一个平衡。你可以在平衡子树的同时把它们的权重加起来。

所以算法是:

static const float BALANCE_WEIGHT = 10.0f;
// return total weight of the balance and everything on it, including the 10.0f that this balance weighs
// modify the .weight_left or .weight_right of every node that needs it, in the subtrees of this node
float balance(struct balance storage[], int current)
{
    float lweight = 0, rweight = 0;
    // C++ can make this more readable:
    // struct balance &cur = storage[current];
    // loop over all the left and then right children, totalling them up
    // depth-first search, since we recurse/descend before doing anything else with the current
    for (int i = storage[current].left ; i >= 0 ; i = storage[i].next )
        lweight += balance(storage, i);
    for (int i = storage[current].right; i >= 0 ; i = storage[i].next )
        rweight += balance(storage, i);

    lweight += storage[current].weight_left;
    rweight += storage[current].weight_right;
    float correction = fabsf(rweight - lweight);
    // modify the data structure in-place with the correction.
    // TODO: print, or add to some other data structure to record the changes
    if (lweight < rweight) {
        storage[current].weight_left += correction;
    } else {
        storage[current].weight_right += correction;
    }
    return BALANCE_WEIGHT + rweight + lweight + correction;
}

要记录您所做的更改，要么在数据结构中使用额外的字段，要么在从深度优先平衡返回时销毁原始数据(因为不再需要它)。例如，如果左侧需要添加权重，则存储.weight_left = correction; .weight_right = 0;，否则执行相反操作。

如果有一个全局数组，这个实现将使用更少的堆栈空间，而不是每次递归调用都必须传递storage指针。这是一个额外的值，必须在寄存器调用ABI中保存/恢复，并且直接占用堆栈调用ABI(如32位x86)的额外空间。

所有涉及当前节点的weight_left和weight_right的计算都发生在最后，而不是在开始时读取它们，然后为了+= read-modify-write而重新读取它们。编译器无法进行此优化，因为它不知道数据结构没有循环，导致balance(subtree)修改其中一个权重。

由于某些原因，x86 gcc 5.2 -O3将此编译为非常大的代码。-O2更理智。

这个答案也会给出工作代码，这次是PHP。

一些重要的观察:

• 即使给定的例子从未在任何余额的任何一侧放置多个余额，但允许多个余额位于余额的一侧;
• 不能保证只有一个根平衡，房间里可能有几个独立的堆栈;
• 输入格式将允许一个平衡在多个其他平衡上休息，或者在同一平衡侧休息多次，甚至休息自己。假定这样和其他循环输入将被认为无效;
• 条件"选择在最低余额上添加额外重量的方式"相当于说"您只允许在每个余额的一侧添加重量，不得同时添加"

定义了四个函数:

• parseInput接受一个输入字符串，并返回一个以逻辑方式表示数据的对象数组;
• addWeights获取余额的索引(ID)并计算应该在其哪一侧添加权重，并将该权重存储在新属性中。该计算使用递归来计算位于该余额两侧的所有余额的权重，然后用添加的权重对这些余额进行平衡。如果检测到循环，则抛出错误，因此也可以防止无限递归;
• balance访问所有余额，如果它们尚未平衡，则调用上面的addWeights。这将涵盖多个根平衡配置;
• outputString接受完成的结构并返回预期输出格式的字符串。

数据结构是一个对象对数组。示例数据将被转换为以下形式，在计算过程中添加 adddedweight 属性:

[
  [
    { 'weight' => 0, 'balances' => [1], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' => [2], 'addedWeight' => 14 }
  ], [
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' => 10 },
    { 'weight' => 0, 'balances' => [3], 'addedWeight' =>  0 }
  ], [
    { 'weight' => 3, 'balances' =>  [], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  3 }
  ], [
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  0 }
  ]
]

代码中的注释应该解释最重要的部分:

function parseInput($input) {
    $lines = preg_split('/('r'n|'n)/', $input, null, PREG_SPLIT_NO_EMPTY);
    $count = (int) array_shift($lines); // we don't need this item
    $balances = array();
    $side = array();
    foreach($lines as $line) {
        // get the numbers from one line in an array of numbers
        $args = array_map('intval', explode(' ', $line));
        $obj = new stdClass();
        // first number represents the weight
        $obj->weight = array_shift($args);
        // all other numbers represent IDs of balances
        $obj->balances = $args;
        // collect this as a side, next iteration will fill other side
        $side[] = $obj;
        if (count($side) == 2) {
            // after each two lines, add the two objects to main array
            $balances[] = $side;
            $side = array();
        }
    }
    return $balances;
}
function addWeights(&$balances, $id) {
    if ($id == -1) {
        // There is no balance here: return 0 weight
        return 0;
    }
    // Check that structure is not cyclic:
    if (isset($balances[$id][0]->addedWeight)) {
        throw new Exception("Invalid balance structure: #$id re-encountered");;
    }
    $total = 10; // weight of balance itself
    $added = 0;
    foreach($balances[$id] as &$side) {
        // get the direct weight put in the balance: 
        $weight = $side->weight;
        // add to it the total weight of any balances on this side,
        // by using recursion
        foreach($side->balances as $balanceId) {
            $weight += addWeights($balances, $balanceId);
        }
        // calculate difference in left/right total weight
        $added = $weight - $added;
        $total += $weight;
        // create new property with result
        $side->addedWeight = 0;
    }
    // set either left or right added weight:
    $balances[$id][$added > 0 ? 0 : 1]->addedWeight = abs($added);
    $total += abs($added);
    return $total;
}
function balance(&$balances) {
    // If the only root balance was at index 0, we could just 
    // call addWeights($balances, 0), but it might be elsewhere
    // and there might even be multiple roots:
    foreach($balances as $index => $balance) {
        if (!isset($balance[0]->addedWeight)) {
            addWeights($balances, $index);
        }
    }
}
function outputString(&$balances) {
    $output = '';
    foreach($balances as $index => $balance) {
        $output .= "$index: {$balance[0]->addedWeight} {$balance[1]->addedWeight}'n";
    }
    return $output;
}

下面是它的用法:

// test data
$input =
"4
0 1
0 2
0
0 3
3
0
0
0";
// 1. transform input into structure
$balances = parseInput($input);
// 2. main algorithm
balance($balances);
// 3. output the result in desired format
echo outputString($balances);

输出是:

0: 0 14
1: 10 0
2: 0 3
3: 0 0

概览

这个问题需要一个树状结构来表示基于平衡的平衡。为了解决这个问题，你需要能够:-

1. 查找所有余额。这需要某种形式的递归函数，你可以访问左和右子节点。

2. 计数权重。从给定的天平中，求出其左侧和右侧的重量

3. 添加权重。考虑到问题表明权重需要首先添加到最低的平衡，然后你反复查看树中没有子平衡，或者有已经平衡的子平衡。