php - 我需要一个提示才能开始这个编程难题

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 上没有其他天平，所以我们需要做的就是通过在其右侧放三磅来平衡它。现在它总共重 16 磅。天平 1 右侧有天平 3，重 10 磅，所以我们只在其左侧放 10 磅。天平 1 的总重量为 30 磅。天平 0 左侧有天平 1(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. 在 InitialPounds 的帮助下更新它的 TotalWeight。

3. 现在查看节点的其他兄弟节点是否设置了 TotalWeight。如果否，请在那里设置递归函数的根并执行。

4. 如果是，计算差异并更新您坐的位置的AddedPounds。现在转到父级并更新其 TotalWeight。 (不要忘记为余额添加 10p)。然后去找祖 parent 重复3。

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

此答案适用于您要求的入门。