题解

思路

先考虑恰好花费 $C$ 元。

做法

若 $C=2n+1$，最终一定进行了奇数次取负，可得到区间 $[-B-n,-B+n]$；若 $C=2n>0$，可以不用取负得到端点 $B-n$，或使用正偶数次取负后在剩余预算内增减，合起来得到区间 $[B-n,B+n-1]$，而 $C=0$ 时只有 $B$。

花费恰为 $k$ 元能得到的数在多花两次取负后仍可得到，所以“不超过 $C$”只需合并恰花 $C$ 与 $C-1$ 元的两个区间。分别计算区间长度，再减去交集长度即可。

复杂度

时间复杂度为 $O(1)$，使用 128 位整数处理中间端点与计数。