题解：CF2128C Leftmost Below

S_P_A_ · 2025-08-19 14:57:53 · 题解

设某个时刻 a 数组为 a_1, \ldots, a_n ，

由于 a 数组中每个数的值只能增大

故：所有 1 \leq i \leq n 都有 a_i \leq b_i 。

若要让 a_i 增加 x，则对于 1 \leq j \leq i-1 ，都有 a_i < x \leq a_j 。

变换，得

于是，对于后者显然有

由于 a 要变成 b，则最后一次操作是 x + a_i = b_i 。

又由 a_i < x 得 a_i+x<2x，

所以 b_i<2x。

又因为 2x < 2 \min_{1 \leq j \leq i-1}b_j ,

所以 b_i < 2\min_{1 \leq j \leq i-1}b_j。

综上所述，要使 a 变成 b，b 数组必须满足后边的数小于前面数的二倍（必要性得证）。

当 i > j 且 b_i < 2\min_{1 \leq j \leq i-1}b_j，必然可使 x_1 = \min_{1 \leq j \leq i-1}b_j,x_2 = b_i-\min_{1 \leq j \leq i-1}b_j （充分性得证）。

程序就显然了。记录前面数的最小值（记录 \texttt{minn}），若当前数 b>=2minn 则判定为不能，否则可以。