题解

思路

因为绝对值和与元素顺序无关，可设 $B_1\le B_2\le\cdots\le B_L$；最优解中还可令 $B_1=0$，否则所有元素同时减一不改变绝对值和，却会减少最大值。

做法

令 $C_k=B_{k+1}-B_k\ge0$，每个间隔 $C_k$ 被左侧 $k$ 个元素与右侧 $L-k$ 个元素之间的所有数对计算，因而条件等价于 $\sum_{k=1}^{L-1}k(L-k)C_k=A_i$，而 $\max(B)=\sum C_k$。

问题因此是以 $k(L-k)$ 为物品重量、每件代价为 $1$ 的完全背包最小化。对所有询问只需预处理到 $M=\max A_i$；由对称性只考虑 $k\le L/2$，且当 $k(L-k)>M$ 时后续权值都不可能出现在答案中。

复杂度

可用的权值不超过 $O(\sqrt M)$ 个，因而时间复杂度为 $O(N+M\sqrt M)$，空间复杂度为 $O(M)$。