二分算法

• 若题目中和平均数有关，可以考虑将数列中所有数都减去平均数，再看最大子段和能否大于0。
• 二分的 check 函数里写什么算法都可以。比如SPFA、DP等等。我想出了把DP写在check函数里
• 从 \(n\) 个一次函数 \(y_i=k_i x+b_i\) 中选出若干，使 \(\sum{y_i}\) 不能超过上限(或不能低于下限) \(lim\) ，求 \(x\) 的最值。可以考虑使用二分+nth_element，计算指定 \(x\) 下 \(\sum{y_i}\) 的最值，和 \(lim\) 比较
• 从数据范围入手。Ex: 对于 \(100\%\) 的数据，满足 \(0\leq M\leq N\leq 5\times 10^4\)，\(1\leq L\leq 10^9\)，\(0\leq D_i\leq L\)。 我们注意到 \(M\)，\(N\) 的范围不大，但 \(L\) 很大。因此我们优先考虑枚举 \(M\)，\(N\) 的算法，而不需要枚举 \(L\) 的算法。
• 一定情况下，可以将数列中各个元素的奇偶性转换为它们求和的奇偶性。因为一个奇数和若干偶数的和还是奇数，而偶数的和就是偶数了。
• 题目中若包含 “若无解，则输出-1” 等类似的意思，可先判断是否有解，再计算答案。