一些 trick（13）| how to use binary search

· · 算法·理论

例题 1. CF1373F

给定正整数序列 a_1,a_2,\cdots,a_n 和 b_1,b_2,\cdots,b_n，求是否存在非负整数序列 c_1,c_2,\cdots,c_n 和 d_1,d_2,\cdots,d_n 满足：

\begin{cases} c_i+d_i\ge a_i&1\le i\le n\\ c_i+d_{i\bmod n+1}\le b_i&1\le i\le n \end{cases} 考虑确定 $d_1$，则可以贪心地确定 $c_1,d_2,c_2,\cdots$，因此可以判定 $d_1$ 可行性。 发现如果不可行，则有两种情况：某个 $c_i$ 必须 $<0$ 或者最终的 $c_n+d_1>b_i$。前者说明要增加 $d_1$，后者说明要减少 $d_1$，维护可行区间 $d_1\in [\ell,r]$ 二分即可。 例题 2. [P7624](https://www.luogu.com.cn/problem/P7624) B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 $n$ 个车站，**相邻两个车站之间的铁路长度为正整数**。现在小雪进行了一些观察，得到了 $m$ 条信息，第 $i$ 条信息是如下形式之一： 1. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不小于一个给定的值 $L_i$（$S_i$ 和 $T_i$ 是两个车站）； 2. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不大于一个给定的值 $L_i$。 小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。 保证 $3 \le n \le 500$，$1 \le m \le 500$，$1 \le L_i \le 10^9$。 可以发现，如果确定了总长度，则容易差分约束判定是否可行。只需要找到任意一个可行的长度，在其左右二分即可。 为什么是区间？因为差分约束建图的每个环的非负条件都给了总长度一个不等式，因此可行解是区间。这启发我们对于一个不可行解，找到它的一个负环，它所有边的边权和一定形如 $aL+b$，其中 $L$ 为总长度。根据 $a$ 的正负判断需要增加还是减少 $L$ 即可。 已经加入 [一些 trick](https://www.luogu.com.cn/article/o0yp5tx3)。