志愿者调配

难度: Medium

「力扣挑战赛」有 `n` 个比赛场馆（场馆编号从 `0` 开始），场馆之间的通道分布情况记录于二维数组 `edges` 中，`edges[i]= [x, y]` 表示第 `i` 条通道连接场馆 `x` 和场馆 `y`(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 `m` 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种： 1. 将编号为 `idx` 的场馆内的志愿者人数减半； 2. 将编号为 `idx` 的场馆相邻的场馆的志愿者人数都加上编号为 `idx` 的场馆的志愿者人数； 3. 将编号为 `idx` 的场馆相邻的场馆的志愿者人数都减去编号为 `idx` 的场馆的志愿者人数。所有的调配信息记录于数组 `plans` 中，`plans[i] = [num,idx]` 表示第 `i` 天对编号 `idx` 的场馆执行了第 `num` 种调配方案。在比赛结束后对调配方案进行复盘时，不慎将第 `0` 个场馆的**最终**志愿者人数丢失，只保留了**初始**所有场馆的志愿者总人数 `totalNum` ，以及记录了第 `1 ~ n-1` 个场馆的**最终**志愿者人数的一维数组 `finalCnt`。请你根据现有的信息求出初始每个场馆的志愿者人数，并按场馆编号顺序返回志愿者人数列表。 **注意：** - 测试数据保证当某场馆进行第一种调配时，该场馆的志愿者人数一定为偶数； - 测试数据保证当某场馆进行第三种调配时，该场馆的相邻场馆志愿者人数不为负数； - 测试数据保证比赛开始时每个场馆的志愿者人数都不超过 `10^9`； - 测试数据保证给定的场馆间的道路分布情况中不会出现自环、重边的情况。 **示例 1：** >![image.png](https://pic.leetcode-cn.com/1630061228-gnZsOz-image.png) > 输入： >`finalCnt = [1,16], totalNum = 21, edges = [[0,1],[1,2]], plans = [[2,1],[1,0],[3,0]]` > > 输出：`[5,7,9]` > > 解释： > ![image.png](https://pic.leetcode-cn.com/1630061300-WuVkeF-image.png){:height=200} **示例 2 ：** > 输入： >`finalCnt = [4,13,4,3,8], totalNum = 54, edges = [[0,3],[1,3],[4,3],[2,3],[2,5]], plans = [[1,1],[3,3],[2,5],[1,0]]` > > 输出：`[10,16,9,4,7,8]` **提示：** - `2 <= n <= 5*10^4` - `1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)` - `0 <= edges[i][0], edges[i][1] < n` - `1 <= plans.length <= 10` - `1 <= plans[i][0] <=3` - `0 <= plans[i][1] < n` - `finalCnt.length = n-1` - `0 <= finalCnt[i] < 10^9` - `0 <= totalNum < 5*10^13`

Submission

运行时间: 286 ms

内存: 38.2 MB

class Solution:
    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:
        # 用虚数1j 表示场馆0在最后一天的人数
        # 倒推，然后解方程
        n = len(finalCnt) + 1
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        v = [1j] + finalCnt
        for scheme, venue in reversed(plans):
            if scheme == 1:
                v[venue] *= 2
            elif scheme == 2:
                for nxt in g[venue]:
                    v[nxt] -= v[venue]
            else:
                for nxt in g[venue]:
                    v[nxt] += v[venue]
        
        t = sum(v)
        zero = (totalNum - t.real) // t.imag
        return [floor(x.real + x.imag * zero) for x in v]

Explain

这个题解采用的是数学倒推的方法。首先，我们知道最终各个场馆的志愿者人数，但是需要求出初始时各个场馆的志愿者人数。为了实现这一点，我们可以从最后一天的调配方案开始，逆向操作，直到回到第一天。在这个过程中，我们使用虚数1j来表示第0个场馆的人数，这样可以将所有场馆的人数表示为实数和虚数的组合，其中实数部分表示最终人数，虚数部分表示相对于第0个场馆的人数变化。最后，通过总人数和各场馆人数之间的关系，可以解出第0个场馆的初始人数，进而得到所有场馆的初始人数。

时间复杂度: O(E + PN)

空间复杂度: O(N + E)

class Solution:
    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:
        # 用虚数1j 表示场馆0在最后一天的人数
        # 倒推，然后解方程
        n = len(finalCnt) + 1
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        v = [1j] + finalCnt
        for scheme, venue in reversed(plans):
            if scheme == 1:
                v[venue] *= 2
            elif scheme == 2:
                for nxt in g[venue]:
                    v[nxt] -= v[venue]
            else:
                for nxt in g[venue]:
                    v[nxt] += v[venue]
        
        t = sum(v)
        zero = (totalNum - t.real) // t.imag
        return [floor(x.real + x.imag * zero) for x in v]

Explore

在这个解决方案中，使用虚数来表示第0个场馆的人数是为了在逆向操作过程中能够同时跟踪和计算每个场馆人数相对于第0个场馆的变化。虚数部分（1j表示）用来模拟第0个场馆的人数变化，而实数部分用来表示其他场馆的人数。这种方法的优势在于，它可以在不知道具体初始人数的情况下，通过算术运算维护场馆间人数的相对变化。这样，最终只需解一个方程就能找出第0个场馆的实际初始人数，从而计算出所有场馆的初始人数。

逆向操作中，第二种和第三种调配方案涉及到将一个场馆的人数加到或者减去相邻场馆的人数。这种操作可以直接进行，因为它们是调配方案的逆操作，即如果原来是增加，则逆向操作时就减少；如果原来是减少，则逆向操作时就增加。这样的操作不会改变最终的总人数，因为只是在场馆之间重新分配人数，没有增加或减少总人数。

在倒推结束后，通过解方程来确定第0个场馆的初始人数，确保它是整数的关键在于方程设置的合理性和数学计算的准确性。方程是基于总人数和每个场馆人数变化的关系建立的。如果所有输入数据（如总人数和最终各场馆人数）都是整数，并且所有操作（如加倍或加减相邻场馆人数）都保持整数的性质，那么解出的第0个场馆的初始人数也应该是整数。这依赖于问题的设定和算法的正确实现。