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

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右侧有三个平衡重,重10磅,所以我们只在左侧放10磅.Balance 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

我试过,但我猜编程真的很糟糕.我应该从哪里开始？请不要发布解决方案; 我想学习.

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在 it's 的帮助下更新它的InitialPounds。

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

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

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

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