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

Question

你有一个房间，里面装满了天平和重量。每个天平重10磅，当它左右两边的重量总和完全相同时，就被认为是完全平衡的。您已经在一些余额上放置了一些权重，并且您已经将一些余额放置在其他余额上。给出平衡是如何排列的描述，以及每个平衡上有多少额外的重量，确定如何增加平衡的重量，使它们都完全平衡。

平衡所有东西的方法可能不止一种，但始终选择将额外重量放在最低余额的方法。

输入文件将以一个整数N开始，该整数指定有多少余额。余额0由行1和2指定，余额1由行3和4指定，依此类推...每对行的格式如下：

WL <balances>
WR <balances>

WL和WR分别表示添加到左侧和右侧的权重。是此余额的那一侧的其他余额的空格分隔列表。可以包含零个或多个元素。

考虑以下输入：

4
0 1
0 2
0
0 3
3
0
0
0

Balance 0 has balance 1 on its left side and balance 2 on its right side
Balance 1 has balance 3 on its right side
Balance 2 has three pounds on its left side
Balance 3 has nothing on it

由于天平3上没有任何东西，它已经完全平衡了，总重量为10磅。平衡2上没有其他的平衡，所以我们需要做的就是把3磅放在它的右边来平衡它。现在它的总重量是16磅。平衡1的右边是平衡3，重10磅，所以我们只把10磅放在左边。天平1的总重量为30磅。余额0在其左侧(30磅)，余额2在其右侧(16磅)，我们可以通过在右侧增加14磅来平衡它。

输出应为N行长，第n行列出添加到第n个余额的权重，格式如下：

<index>: <weight added to left side> <weight added to right side>

因此，此问题的输出将为：

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

我试过了，但我想我真的不擅长编程。我应该从哪里开始呢？请不要张贴解决方案；我想学习。

Answer 1

这是你的树

           (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. 在它的TotalWeight的帮助下更新它的TotalWeight，看看这个节点的另一个同级是否设置了它的。如果NO，设置你的递归函数的根并执行。
3. If YES，计算差值并更新你所在位置的AddedPounds。现在转到父对象并更新其TotalWeight。(别忘了为余额加10便士)。然后转到祖父母并重复3.

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

此答案适用于您所要求的初学者。

Answer 2

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

这个问题很古老，而且看起来很有趣，所以我只是在几个类似提示的开头段落之后，用C语言解决了它，而不是像这样加了标签的PHP。我使用了详细的变量名和注释，所以它应该作为伪代码工作。我打算写类似C语言的伪代码，但从来没有碰到过任何值得总结的东西。

这个问题的主要复杂之处在于，您不能使用二进制树，因为单个余额可以在其中一个或两个pans上有多个其他余额。这里最简单的方法可能是节点的链表，其中每个节点都有左子节点和右子节点，还有一个兄弟指针。为了让所有的余额都位于余额的左边，遍历兄弟指针的链表，从你正在查看的余额节点的左子节点开始。

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

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的计算都在最后进行，而不是在开始时读取它们，然后重新读取它们以进行+=读取-修改-写入。编译器无法进行这种优化，因为它无法知道数据结构是否没有循环，从而导致balance(subtree)修改其中一个权重。

由于某种原因，x86 gcc 5.2 -O3 compiles this to really huge code。使用-O2更明智。clang可以使用-O3，但缺少一些优化。

Answer 3

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

一些重要的观察结果：

• 尽管给定的示例从未在任何余额的任一侧放置多个余额，但允许多个余额位于余额的一侧；
• 不能保证只有一个根余额，房间中可能有多个独立的堆栈；
• 输入格式将允许一个余额在多个其他余额上休息，或者多次在同一余额一侧休息，甚至可以自己休息。假设这样的循环输入和其他循环输入将被认为是无效的；
• 条件“选择在最低余额上添加额外权重的方式”等同于说“您只能在每个余额的一侧添加权重，而不能同时添加两个”

定义了四个函数：

• parseInput获取一个输入字符串，并返回一个表示逻辑way;
• addWeights中数据的对象数组，获取余额的索引(ID)，计算应该在余额的哪一侧添加权重，并将该权重存储在一个新属性中。该计算使用递归来计算此余额两边的所有余额的权重，在这些余额通过添加的权重进行平衡之后。如果检测到周期，它就会抛出一个错误，因此也会阻止无休止的recursion;
• balance访问所有余额，如果它们还没有平衡，就会调用上面的addWeights。这将涵盖多个根余额configurations;
• outputString采用完整的结构并返回预期输出格式的字符串。

数据结构是对象对的数组。示例数据将转换为以下内容，并在计算过程中添加addedWeight属性：

[
  [
    { '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