如果不该发在这请@我 违规紫衫
我感觉这篇题解写错了,看了半小时不知道怎么推的。
题解 P7302 [NOI1998] 免费的馅饼
第二段这里
这里的 j 满足 ∣pi−pj∣≤2(ti−tj),于是接下来的问题是如何维护每个 i 对应的 j 的集合了。于是将 j 的条件式展开,得到
{pi−2ti≤pj−2tjpi+2ti≥pj+2tj(pi≤pj)(pi≥pj)
在分析这个推导过程时,发现了以下错误(这里用ai生成了,ai描述的比我清楚):
-
不等式展开错误:
- 原始不等式为 ∣pi−pj∣≤2(ti−tj)。
- 根据绝对值的定义,正确展开应为两种情况:
- 当 pi≥pj 时,不等式变为 pi−pj≤2(ti−tj),即 pi−2ti≤pj−2tj。
- 当 pi<pj 时,不等式变为 pj−pi≤2(ti−tj),即 pj+2tj≤pi+2ti。
- 但原推导中错误地将两种情况的条件(pi≤pj 和 pi≥pj)与展开后的不等式组合,导致逻辑矛盾。
-
条件与不等式不匹配:
- 原推导中的第一个不等式 pi−2ti≤pj−2tj 对应的条件应为 pi≥pj,而非 pi≤pj。
- 原推导中的第二个不等式 pi+2ti≥pj+2tj 对应的条件应为 pi<pj,而非 pi≥pj。
修正后的正确推导应为:
{pi−2ti≤pj−2tjpi+2ti≥pj+2tj(pi≥pj)(pi<pj)