小米笔试

第一题：本质上是求哪个题会的人最多，考虑到直接把每个区间暴力加起来会 T，于是采用差分的思想，对 l~r 这一段整体+1，对差分数组而言，只需要 d[l]++，d[r + 1]-- 即可。最后对差分数组做一个前缀和即可还原为原数组，原数组的最大值就是 ans。 第二题：记 dp[i] 表示上一个站建设在位置 i 的最小花费，则 dp[i] 必然是从 dp[0]、dp[1]、...、dp[i - 1] 转移过来，由于 m 只有 1000，直接暴力枚举这些位置 j，然后转移是 dp[i] = min(dp[i], dp[j] + dis_sum[j + 1][i] + c[i])。 其中，dis_sum[l][r] 表示将 l~r 这一段的包裹都送到 r 的距离和，这个需要提前预处理，不然每次都算一遍复杂度会炸。 预处理的方法也简单，首先 dis_sum[i][i] 可以直接得到（定义为第 i-1 个站到第 i 个站之间的包裹全部送到 i 的距离和），其次 dis_sum[l][r] 可以从 dis_sum[l][r - 1] 转移过来，转移的时候只需要知道 l ~ r-1 这一段有多少包裹就行，记这个数量为 cnt，则 dis_sum[l][r] = dis_sum[l][r - 1] + cnt * (b[r] - b[r - 1]) + dis_sum[r][r]。其中 cnt 可以用前缀和预处理到 O(1)。 最后的答案从 dp[k] dp[k+1] ... dp[m] 中取最小值，其中 k 是比所有包裹都远的第一个位置。

蹲蹲题解

蹲