hiho一下第109周《Tower Defense Game》题目分析

1
1

题目大意

给定一颗以1为根节点的树,每个节点有一个购入价格p和卖出价格q

进入一个节点时需要花费p,离开时可以收回q,每个节点只产生一次购入和卖出。

请你选择一个遍历的顺序,要求在遍历的过程中身上的钱数不小于0,且出发时带的钱数最少。

按照遍历的顺序是指:当你选择了一颗子树之后,你需要将这个子树全部走完,才能选择其他子树

解题思路

该题为一道树形图上的贪心问题。

我们每一步的决策在于:当遍历到一个根时,对于其拥有的若干颗子树,应该以怎样的顺序来遍历这些子树

先将问题简化为二叉树,并且两颗子树都只有根节点:

首先我们选择左边的路径,则需要携带的钱数为:

经过1: L1 = p1

经过2: L2 = p1-q1+p2

经过3: L3 = p1-q1+p2-q2+p3

然后考虑走右边的情况:

经过1: R1 = p1

经过3: R2 = p1-q1+p3

经过2: R3 = p1-q1+p3-q3+p2

对于这6个值,我们要求的是min( max(L1, L2, L3), max(R1, R2, R3) )

由于在题目中已经明确说明总是有p≥q,可以肯定有L3≥R2,R3≥L2,所以可以直接将L2R2排除。

又因为1是必经之路,因此在选择左右时,实际上需要比较的只有L3R3

我们将L3R3换一种形式表示:pSum = p1+p2+p3, qSum = q1+q2+q3,则L3=pSum-qSum+q3,R3=pSum-qSum+q2

L3>R3,则有q3>q2,此时要选择的是R3,即走右路;

L3<R3,则有q2>q3,此时要选择的是L3,即走左路。

由于pSumqSum的值是确定的,因此实际上我们只需要根据q2q3的值就可以选择走哪边。

最后的结论也就是:对于二叉树的情况,我们选择q值大的一边先走,一定能保证结果值最小


那么接下来将这个结论推广至多叉树的情况:

对于多叉树的情况,我们将子树按照q值从大到小的顺序,一定能保证结果值最小

这是由于q值之间的大小顺序是绝对的,假设3个子节点分别为A,B,C,若qA≥qB,qB≥qC,则一定有qA≥qC

不妨举个例子:

根据q值,对应的6种遍历顺序分别为:

1,2,3:需要带钱8
1,3,2:需要带钱7
2,1,3:需要带钱8
2,3,1:需要带钱7
3,1,2:需要带钱7
3,2,1:需要带钱6


那么还有一个问题,一个节点的pq是直接给定的,我们应该如何来求一颗子树的ptqt(为了便于区分,我们将树的pq记为ptqt)?

在计算过程中,我们采用递归的从根节点开始遍历。在计算当前节点时,我们需要将其子树的pq都先计算出来。

因此在计算当前子树时,我们已经知道了根节点的pq,以及每颗子树的ptqt(记作pt1,pt2,pt3,...qt1,qt2,qt3,...,并且满足qt1≥qt2≥qt3≥...)。

在该题中所有节点的总购买钱数不会超过200,000,000,不妨设置一个初始钱数wallet = 200000000

同时我们还需要一个值minWallet,来记录钱包钱数最少时的值,初始也为200,000,000。

首先处理根节点:

wallet = wallet - p
If (minWallet > wallet) Then
    minWallet = wallet
End If
wallet = wallet + q

接下来处理每个子树:

For i = 1 .. chdNumber
    wallet = wallet - pt[i]
    If (minWallet > wallet) Then
        minWallet = wallet
    End If
    wallet = wallet + qt[i]
End For

最后可以得到整个树的pq分别为:

pt[root] = 200000000 - minWallet // 遍历这颗树至少需要的钱数
qt[root] = wallet - minWallet    // 最后的钱数-花费的钱数=返还的钱数

完整的伪代码为:

DFS(rt):
    wallet = 200000000
    minWallet = 200000000
    // 先递归处理每个子树
    For each child i of rt
        DFS(i)
    End For
    // 对该根节点的所有子树按照qt值排序
    sortByQt(children)
    // 处理根节点
    wallet = wallet - p[rt]
    If (minWallet > wallet) Then
        minWallet = wallet
    End If
    wallet = wallet + q[rt]
    // 处理子树
    For each child i of rt
        wallet = wallet - pt[i]
        If (minWallet > wallet) Then
            minWallet = wallet
        End If
        wallet = wallet + qt[i]
    End For
    // 记录子树
    pt[rt] = 200000000 - minWallet
    qt[rt] = wallet    - minWallet

最后所求的结果是pt[1]

由于在每一颗子树都使用了排序,最后这个算法的时间复杂度为O(NlogN),即使在N为10000的数据下,也能够顺理通过。

3 answer(s)

0

由于在题目中已经明确说明总是有p≥q,可以肯定有L3≥R2,R3≥L2,所以可以直接将L2和R2排除。

这里是怎么推导出来的?

2

题解中间有一段比较难理解,我梳理一下自己的思路,交流一下。

首先L1和R1都可以不看了。

(1)如果max(L2, L3) >= max(R2, R3),说明走右边开销小或者相等,应该选右边。

(2)如果max(L2, L3) <= max(R2, R3),说明走左边开销小或者相等,应该选左边。

题目中已经明确说明总是有p≥q,可以肯定有L3≥R2, R3≥L2,那么为什么就可以直接把L2和R2排除呢

因为 max(L2, L3)>= L3 >=R2 ,如果我们又比较了L3>R3,那么说明L3分别大于等于R2和R3

max(L2, L3)>= L3>= max(R2,R3) ,即条件(1)。所以只要L3>R3,就应该选右边。

同理,只要L3< R3,就应该选左边。

0

输入处理的时候,a 和 b 之间有一条边,是不是一定a是父节点,还是说有可能b是父节点?

  • 哎 果然是建树建的有问题,看来不能自己妄加揣测加条件...

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享