8月16日淘天算法岗笔试复盘：三道编程题思路和AC代码

哈喽，牛客的各位小伙伴们，大家好！

做完淘天的题目，感觉脑细胞烧了不少。整体感觉题目质量很不错，既考察了思维的灵活性，也涉及了经典数据结构的应用。下面就让我们一起来看看吧！

第一题

题目大意

给定 个带有能量值 的宝石。可以执行一种操作：将宝石 的能量转移到宝石 上，使 变为 ， 变为 。目标是最大化所有位置的前缀最大能量值之和，即 。

考点分析

这道题的本质是对数组元素进行重新分配，以达到最优的目标函数值。核心考察的是 贪心算法 的思想。需要洞察到，为了让前缀最大值之和最大，应该让这个前缀最大值尽可能早地出现，并且数值尽可能大。

样例输入与输出

2
3
3 2 -1
1
-1

15
-1

解题思路

理解操作的本质是关键。多次操作后，可以将任意一部分宝石的能量聚合到任意一个位置，而其他被转移能量的宝石位置则变为 。

为了最大化 ，一个自然而然的贪心想法是，让序列的前缀最大值尽可能大且保持稳定。

1. 构造最优序列：最好的策略是创造一个“巨无霸”宝石，放在数组的第一个位置。这样一来，、、...、 都会被这个 的值所主导。
2. 贪心选择：什么样的“巨无霸”最好？当然是把所有“正向收益”都集中起来。所以，将所有能量值为正数的宝石，通过融合操作，全部集中到 位置。其他所有负数和 的宝石可以放在后面，或者通过操作将它们的能量值也变成 。
3. 计算结果：
   • 如果存在正能量宝石：将所有正能量值求和，得到 positive_sum。将这个和放在 位置，其他位置可以视为 或负数。由于 positive_sum > 0，并且大于任何负数或 ，那么对于所有的 ，前缀最大值 都将是 positive_sum。因此，最终答案就是 。
   • 如果全是负数或零：
     • 若宝石数量 ，总可以通过操作将能量都集中到一个宝石上，让至少一个其他宝石能量变为 。例如，把 的负能量转移给 ，然后 变为 。我们可以把 变成所有能量之和，其他 个位置都变成 。此时序列可以是 [sum, 0, 0, ..., 0]。前缀最大值序列将是 [sum, 0, 0, ..., 0] (因为 sum 是负数)，总和为 sum。但我们可以做得更好：把一个负能量宝石 的能量转移给 ，然后把 的能量再转移给 ... 最终把所有能量集中到一个位置，其他位置全为 。我们可以把 放在第一个位置，比如把 的能量给 ， 变 ，再把 的能量给 .... 这样可以构造出 [0, sum, ...] 这样的序列，使得前缀最大值都为 ，总和为 。所以，只要 ，答案就是 。
     • 若宝石数量 ，无法进行任何操作，答案就是它本身的能量值 。

AC代码 (Python)

import sys

def solve():
    """
    处理单次测试数据的函数
    """
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        gems = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    # 1. 贪心策略：计算所有正能量宝石的总和
    positive_sum = sum(val for val in gems if val > 0)
    
    # 2. 根据是否存在正能量来决策
    if positive_sum > 0:
        # 如果存在正数，最优解是将所有正能量集中于首位
        # 此时每个位置的前缀最大值都是 positive_sum
        result = positive_sum * n
        print(result)
    else:
        # 如果不存在正数 (全是负数或零)
        if n == 1:
            # 只有一个宝石，无法操作，答案就是其本身
            print(gems[0])
        else:
            # 可以通过操作将某个位置变为0，并放在首位
            # 使得所有前缀最大值都为0，总和为0
            print(0)

def main():
    """
    主函数，处理多组输入
    """
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

第二题：

题目大意

在一个 的网格中，有 个探险者和 个救援站。救援站位于对角线 上。每个探险者会去距离自己最近的救援站（曼哈顿距离），若有多个最近的，可以任选其一。每个救援站只能救一个人。求最多能救多少人。

考点分析

这道题看似是图论或几何问题，但实际上可以巧妙地转化为一维的 区间调度/区间选点 问题。解题的关键步骤包括：

1. 问题转化：将二维坐标点的匹配问题，转化为一维区间的选择问题。
2. 贪心策略：应用经典的区间调度贪心算法。
3. 效率优化：使用 并查集 (Disjoint Set Union, DSU) 来加速查找过程，避免超时。

样例输入与输出

2 3
1 2
2 1
1 1

2

解题思路

1. 寻找最近救援站区间：对于一个位于 的探险者，他到对角线救援站 的曼哈顿距离为 。

   • 通过简单的数学分析可以发现，当 位于 和 之间时（即 ），距离 取得最小值，为 ，也就是 。
   • 因此，每个探险者 对应一个可选的最近救援站区间 。

2. 转化为区间选点问题：现在问题变成了：有 个区间（探险者），有 个点（救援站 ），每个点最多只能被一个区间占用。求最多能满足多少个区间（救多少人）。

3. 贪心求解：这是经典的区间选点问题。最优贪心策略是：

   • 将所有区间按 右端点 从小到大排序。
   • 遍历排序后的区间 ，对于每个区间，总是尝试分配给它 区间内最靠左的、尚未被占用的 救援站。

4. 并查集优化：如何快速找到“区间内最靠左的可用救援站”？如果暴力遍历，复杂度会很高。这里可以用并查集来优化。

   • 构建一个大小为 的并查集。parent[i] 存储的是 “从位置 开始（包括 ）的第一个可用的救援站”。
   • 初始化时，parent[i] = i for all 。
   • 当要为区间 寻找可用位置时，调用 find(l)，它会返回 的最小可用位置 pos。
   • 如果 pos <= r，说明在区间内找到了可用位置，救援成功。此时，将 pos 位置标记为已占用，方法是执行 union(pos, pos + 1)，即 parent[pos] = pos + 1。这表示下次再查询 pos 时，会自动跳转到查询 pos + 1，实现了快速跳过已占用位置。

AC代码 (Python)

import sys

# 增加递归深度限制，以防大数据量下 DSU 爆栈
sys.setrecursionlimit(2000000)

class DSU:
    """
    带路径压缩的并查集，用于快速查找下一个可用位置。
    """
    def __init__(self, n):
        # parent[i] 表示 >= i 的最小可用救援站编号
        # 多开两个位置作为哨兵，防止边界问题
        self.parent = list(range(n + 2))

    def find(self, i):
        # 路径压缩：在查找的同时将路径上的节点直接指向根节点
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def occupy(self, i):
        # 占用位置i，将其指向下一个可用位置i+1
        # find(i+1) 是为了处理i+1也可能被占用的情况
        self.parent[i] = self.find(i + 1)

def solve():
    try:
        n, m = map(int, sys.stdin.readline().split())
        
        explorer_intervals = []
        for _ in range(m):
            x, y = map(int, sys.stdin.readline().split())
            # 每个探险者对应一个可选的救援站区间 [l, r]
            left, right = min(x, y), max(x, y)
            explorer_intervals.append((left, right))

        # 1. 贪心策略：按区间的右端点升序排序
        explorer_intervals.sort(key=lambda item: item[1])

        dsu = DSU(n)
        rescued_count = 0
        
        # 2. 遍历排序后的区间
        for l, r in explorer_intervals:
            # 3. 查找区间 [l, r] 内最左边的可用救援站
            available_station = dsu.find(l)
            
            # 4. 如果找到的可用位置在区间内
            if available_station <= r:
                rescued_count += 1
                # 占用该救援站，并更新并查集
                dsu.occupy(available_station)
                
        print(rescued_count)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    solve()

第三题：

题目大意

维护一个长度为 的数组。支持两种操作：

1. 单点修改：将 修改为 。
2. 区间查询：查询区间 的方差 (variance)。 方差公式为 ，其中 是区间长度。

考点分析

这是一道将数学知识与高级数据结构相结合的题目。直接按定义计算方差，每次查询都需要 ，无法接受。

1. 数学公式变换：需要将方差公式转换成一个更易于用数据结构维护的形式。
2. 数据结构：支持单点修改和区间求和，自然会想到 树状数组 (Binary Indexed Tree, BIT) 或线段树。树状数组实现更简单，常数更小。

样例输入与输出

5 3
1 2 3 4 5
2 1 5
1 3 10
2 1 5

2.000000
9.840000

解题思路

1. 方差公式推导： 原始方差公式： 展开后得到： 因为 且 : 代入 : 这个公式非常棒，因为它把方差的计算分解成了两个核心部分：区间和 () 和 区间平方和 ()。

2. 树状数组维护： 我们可以用两个树状数组来分别维护这两个值。

   • bit_sum：维护原始值的和。bit_sum[i] 存储 。
   • bit_sum_sq：维护原始值平方的和。bit_sum_sq[i] 存储 。

3. 操作实现：

   • 修改操作 (i, x)：将 的值从 old_val 修改为 new_val = x。
     • 计算差值：delta_val = new_val - old_val。
     • 计算平方差值：delta_sq_val = new_val^2 - old_val^2。
     • 更新第一个树状数组：bit_sum.add(i, delta_val)。
     • 更新第二个树状数组：bit_sum_sq.add(i, delta_sq_val)。
   • 查询操作 (l, r)：
     • 计算区间长度 。
     • 从 bit_sum 中查询区间和 。
     • 从 bit_sum_sq 中查询区间平方和 。
     • 根据公式计算方差：。

AC代码 (Python)

import sys

class FenwickTree:
    """
    树状数组 (Binary Indexed Tree)
    支持单点更新和前缀和查询，时间复杂度均为 O(log n)
    """
    def __init__(self, size):
        self.tree = [0] * (size + 1)

    def add(self, index, delta):
        """在 index 位置增加 delta"""
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & (-index)

    def query(self, index):
        """查询 [1, index] 的前缀和"""
        s = 0
        while index > 0:
            s += self.tree[index]
            index -= index & (-index)
        return s

    def range_query(self, left, right):
        """查询区间 [left, right] 的和"""
        return self.query(right) - self.query(left - 1)

def solve():
    try:
        n, q = map(int, sys.stdin.readline().split())
        initial_energies = list(map(int, sys.stdin.readline().split()))
        
        # 使用 1-based 索引存储原始数组，方便与树状数组对齐
        energies = [0] + initial_energies

        # 初始化两个树状数组
        bit_sum = FenwickTree(n)      # 维护能量值的和
        bit_sum_sq = FenwickTree(n) # 维护能量值平方的和

        for i in range(1, n + 1):
            val = energies[i]
            bit_sum.add(i, val)
            bit_sum_sq.add(i, val * val)

        for _ in range(q):
            line = list(map(int, sys.stdin.readline().split()))
            op_type = line[0]

            if op_type == 1:
                # --- 修改操作 ---
                index, new_val = line[1], line[2]
                old_val = energies[index]
                
                # 计算差值并更新两个树状数组
                delta_val = new_val - old_val
                delta_sq_val = new_val * new_val - old_val * old_val
                
                bit_sum.add(index, delta_val)
                bit_sum_sq.add(index, delta_sq_val)
                
                # 更新原始数组记录
                energies[index] = new_val
            
            else: # op_type == 2
                # --- 查询操作 ---
                l, r = line[1], line[2]
                m = r - l + 1
                
                # 查询区间和与区间平方和
                interval_sum = bit_sum.range_query(l, r)
                interval_sum_sq = bit_sum_sq.range_query(l, r)
                
                # 根据公式 E(X^2) - (E(X))^2 计算方差
                mean = interval_sum / m
                variance = interval_sum_sq / m - mean * mean
                
                print(f"{variance:.6f}")

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    solve()