问题求解II-HW03 题解
Problem A: 最大连续子数组和
- 给定长度为 $n$ 的数组，求和最大的一个连续子数组。
- $n\leq 10^5$。
我们直接给出如下的贪心做法，并尝试说明其正确性：
for (int i = 1; i <= n; i++) {
sum += a[i]; ans = max(ans, sum);
if (sum < 0) sum = 0;
}
我们只要说明每轮循环中，$sum$ 记录的都是以 $a_i$ 结尾的最大和子数组即可。为了说明这点，我们需要想清楚 $sum$ 求的是哪一段的和，即 if 语句丢弃的段有什么性质。
令 $sum$ 上次被置零和本次被置零丢弃的区间为 $[l, r]$，那么我们可以知道：
- $\sum_{k=l}^r a_i < 0$。
- 对于任意 $l\leq t<r$，$\sum_{k=l}^t a_i>0$ (因为一直没有被丢弃)。
由这两条，我们可以推出：对于任意 $l\leq t\leq r$，都有 $\sum_{k=t}^ra_i<0$，从而这一段无论如何都只会对后面产生负数的贡献，因此完全丢弃它是合理且正确的。
Problem B: 芯片测试
- 有 $n$ 个芯片，其中好芯片个数多于坏芯片个数。每次可以挑选两个芯片进行一轮测试，根据测试结果可以得到一定的芯片状态信息。请找出至少一个好的芯片。
- $n\leq 10^5$，交互题。
我们采取如下的策略：随机抽取一个芯片，并拿着它和其他所有芯片各做一次测试。考虑如下两种情况：
- 如果这个芯片是好的，由于初始好芯片数目大于坏芯片数目，所以剩下的芯片中好芯片数目仍不少于坏芯片数目，从而至少有一半的测试实际上是
(好，好)，从而至少有一半的测试结果是(好，好)。 - 如果这个芯片是坏的，那么剩下芯片中好芯片数目仍然大于坏芯片数目，从而少于一半的测试实际上是
(坏，坏)，从而少于一半的测试结果是(好，好)。
综上，一波测试之后我们可以完全确定当前抽取的芯片是好是坏。因为好芯片多于一半，所以多抽几次总能抽到好芯片，可以在时间限制内完成任务。