0816阿里淘天秋招算法岗笔试复盘三道题

#牛客AI配图神器##秋招笔面试记录#

------------------------------------

题目一：

题目大意：
有 n (1 <= n <= 2e5) 颗宝石，每颗有能量值 ai (-n <= ai <= n)。你可以执行任意次“融合”操作：选择两颗宝石 i 和 j，将 j 的能量转移给 i (ai = ai + aj, aj = 0)。目标是最大化所有位置的前缀最大能量值之和，即 sum(max(a1, ..., ai)) for i=1 to n。(T 组数据, 1 <= T <= 1e4)

解法思路：
关键在于理解融合操作的本质是能量的自由分配。为了最大化前缀最大值之和，最优策略是创造一个尽可能大的数，并放在首位。如果数组中存在正数，就把所有正能量的宝石融合到第一颗上，使其能量变为所有正数之和，其余位置变为0或负数。这样每个前缀的最大值都是这个正数之和。如果所有宝石能量都是非正数，若 n>1，则可以通过融合操作造出一个0，使前缀最大值变为0；若 n=1，则无法操作，答案就是其本身的负能量值。

------------------------------------

题目二：

题目大意：
在一片 n x n (2 <= n, m <= 1e6) 的森林中，有 m 名探险者和 n 个救援站。救援站位于对角线 (i, i) 上，每个站只能救一人。探险者会去距离自己最近（曼哈顿距离）的救援站。如果有多个最近的，他们会协调分配以最大化获救人数。求最多能获救的人数。

解法思路：
此题可转化为区间选点问题。对于一个在 (x, y) 的探险者，其到对角线上救援站 (k, k) 的曼哈顿距离为 |x-k| + |y-k|。可以发现，当 k 落在 [min(x,y), max(x,y)] 区间内时，距离是最小且恒定的。因此，每个探险者对应一个可选的救援站区间。问题就变成了：有 m 个区间，n 个点，每个点最多被一个区间选择，求最多能满足多少个区间。这是一个经典的贪心问题：将所有区间按右端点升序排序，然后遍历区间，为每个区间贪心地分配其范围内最靠左的可用救援站。使用并查集可以高效地找到下一个可用的位置。

------------------------------------

题目三：

题目大意：
有 n (1 <= n, q <= 1e5) 个魔法水晶，能量为 ai (1 <= ai <= 1e5)。需要处理 q 次操作，操作分两种：1. 将第 i 个水晶的能量修改为 x；2. 查询区间 [l, r] 内所有水晶能量的波动度（方差）。方差定义为 (1/m) * sum((bi - mean)^2)。

解法思路：
直接计算方差涉及均值，不便于用数据结构维护。关键是对方差公式进行数学变换：Var(X) = E(X^2) - (E[X])^2。对于一个区间，这等价于`(区间平方和 / 区间长度) - (区间和 / 区间长度)^2`。这样，我们只需要维护区间的和与区间的平方和。这可以用两个树状数组（或线段树）来高效实现：一个树状数组维护 `sum(ai)`，另一个维护 `sum(ai^2)`。单点修改时，在这两个树状数组上都进行更新。区间查询时，分别查出区间和与区间平方和，再代入公式计算即可。

具体的详细代码和题解可以戳我主页的文章查看