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

Question

你有一屋子的天平和重量砝码。每个天平的重量为十磅，当其左右两侧的重量之和完全相等时，被认为是平衡的。你已经在某些天平上放置了一些重量，并将其中一些天平放在了其他天平上。给定天平的排列方式以及每个天平上额外增加的重量，请确定如何向这些天平添加重量，使它们都变得平衡。

可能有多种平衡的方式，但总是选择在最低的天平上增加额外的重量。

输入文件将以单个整数N开头，指定有多少个天平。 第0个天平由第1和第2行指定，第1个天平由第3和第4行指定，依此类推... 每对行的格式如下：

WL <balances>
WR <balances>

WL和WR分别表示添加到左侧和右侧的重量。 other_balance是此平衡器两侧上的其他平衡器的用空格隔开的列表。它可以包含零个或多个元素。

考虑以下输入：

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上没有其他天平，所以我们只需要在其右侧放置三磅来平衡它。现在它的总重量为16磅。 天平1右侧有一个称重为10磅的天平3，因此我们只需在其左侧放置10磅即可。天平1的总重为30磅。 天平0左侧有重量为30磅的天平1和右侧有重量为16磅的天平2，我们可以通过在右侧加入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

我尝试了，但我想我真的很菜。我应该从哪里开始？请不要发布解决方案；我想学习。

- Adam

---

考虑将正在发生的事情建模成一棵树形结构，其中每个平衡是一个分支节点，每个重量是一个叶子节点。 - Stuart Golodetz

顺便提一下，我认为这是一个有趣的问题，应该重新开放讨论 - 还有其他几个人也同意我的看法。 - Stuart Golodetz

我支持重新开放这个帖子，这是一个非常有趣的问题。 - aki

我想知道答案。 - rcs20

这是一个非常有趣的问题，我投赞成重新开放。 - joel

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. 使用其InitialPounds的帮助更新其TotalWeight。 3. 现在查看节点的其他兄弟姐妹是否设置了其TotalWeight。如果没有，则将递归函数的根设置在那里并执行。 4. 如果是，则计算差异并更新您所在位置的AddedPounds。现在转到父级并更新其TotalWeight。（不要忘记为天平添加10p）。然后进入祖父母并重复步骤3。

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

此答案是针对您所要求的入门者。

- Charlie

---

每个平衡需要指向一个左孩子和一个右孩子。不需要存储它自己的Idx。此外，您可能希望单独存储左侧和右侧AddedPounds，除非您想使用虚拟平衡处理添加的重量。此外，InitialPounds和TotalWeight可以是递归函数中的局部变量，而不是存储在数据结构中。此外，您没有为处理同一秤上的多个平衡做出任何规定，但我猜您有意将其留出，因为OP只要求一个开始（4年前:P）。 - Peter Cordes

每个递归都不被认为是坐在平衡树的根上，而是在一个平衡板上。 1.请注意我已经说过 "我们正在谈论一个递归函数，它基本上知道在树的任何节点上只有两条路径或没有路径可供跟随". BalanceIdx 用作指示，以显示该 "板" 是否有悬挂的子平衡。2. InitialPounds 和 TotalWeight 不能是局部变量，因为前者是输出的一部分，后者是您将在最后累积的直接输出。感谢审查。 - Charlie

看看我的答案。我通过让递归函数返回该平衡的重量（10磅）加上其盘子上的所有物品（调整后），将子树的权重总和计入本地变量中。使用递归函数可以以这种方式使用本地变量。如果您在不使用递归的迭代遍历树，则无法这样做，但递归为每个子树提供了单独的本地变量实例。无论如何，我想你是说有一个单独的数据结构来表示平衡？像 struct balance { struct pan left, right; }？BalanceIdx索引该数组吗？ - Peter Cordes

Answer 2

这个答案也会提供PHP的工作代码。

一些重要的观察：

• 尽管给定的示例从未在任何天平的一侧放置多个天平，但允许在一侧放置多个天平；
• 不能保证只有一个根天平，房间中可能有几个独立的堆栈；
• 输入格式允许一个天平搭在多个其他天平上，或者多次搭在同一天平的一侧，甚至搭在自己身上。假设这样和其他循环输入将被视为无效；
• 条件“选择在最低天平上增加重量的方式”等价于说“你只能在每个天平的一侧添加重量，而不是两侧都添加”

定义了四个函数：

• parseInput接受一个输入字符串并以逻辑方式返回表示数据的对象数组；
• addWeights接受平衡索引（ID），计算应在其哪一侧添加重量，并将该重量存储在新属性中。该计算使用递归来计算平衡器两侧所有平衡器的重量，这些平衡器在添加重量后已经平衡。如果检测到循环，则会抛出错误，从而防止无限递归；
• balance访问所有平衡器，如果它们尚未平衡，则调用上述addWeights。这将覆盖多个root平衡配置；
• 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

- trincot

---

很好地发现了问题并没有说必须有一个单一的根节点。我甚至没有意识到我在做出这个假设！ - Peter Cordes

谢谢，@PeterCordes，我写了更多的东西，并添加了一个检查来防止进入树循环。我们都知道这纯粹是为了好玩，因为这个问题的日期是2011年，但乐趣在于做而不是奖励。 - trincot

是的，我很开心能让我的解决方案更有效率：与一些更笨拙的解决方案不同，你可以在递归中实时跟踪添加的质量，作为返回值/本地变量。你只需要将任何内容添加到数据结构中，以便按不同顺序从遍历中打印出来。虽然“充满天平的房间”问题的多根部分可能需要对此进行修订。但我不知道是否会费心去做。 - Peter Cordes

事实上，即时计算总重量很好。多根支持在您的代码中很容易实现：您只需要跟踪已访问的节点（例如作为结构体中的附加布尔值）。然后，不要在主函数中使用索引0一次调用balance，而是遍历整个数组，并在尚未访问的任何元素上调用balance（这些是额外的根）。可以通过维护非访问节点的双向链表来进行优化，但我没有选择这样做。 - trincot

很棒的解决方案， 我可以有一个用Python的解决方案吗？ - Akshay Kumar Both

@AkshayKumarBoth，当然可以在Python中实现。你试过了吗？如果你在Python编码方面有特定的问题，请提出一个新的问题。 - trincot

Answer 3

剧透警告：包含完整解决方案（除了读取输入部分）

这个问题相当古老，看起来很有趣，所以我去解决了它（用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;，否则执行相反操作。

---

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

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

由于某种原因，x86 gcc 5.2通过-O3将其编译为非常庞大的代码。使用-O2更加理智。clang使用-O3还可以，但会错过一些优化。

- Peter Cordes

---

好的评论，这不是一个二叉树问题。我之前错过了这个问题，因为提问者给出的例子太简单了。 - trincot

Answer 4

概述

该问题需要一棵树结构来表示平衡状态，以及这些平衡状态所依靠的平衡状态。为了解决这个问题，你需要能够：

1. 找到所有的平衡状态。这需要一种递归函数的形式，可以访问左右子节点。

2. 计算重量。从给定的平衡状态中，找出其左侧和右侧的重量。

3. 添加重量。鉴于问题说明需要先将权重添加到最低的平衡状态，因此你需要反复查找没有子节点或已经平衡过的子节点的平衡状态。

- mksteve