首先我们能够发现，最终得到的答案 \(b\) 一定为下凸的。但是直接求凸壳肯定不行。具体地，答案的凸壳要满足对于每个 \(x\)，\(b_x\) 都是整数，即每段斜率都是整数。
可以发现找到能包住点集，最贴合的一个这样的 \(b\) 数组就是答案，因为题目给定的操作让我们每次都只能扩展最贴紧的点。那么我们先对 \(a\) 求出凸包，然后从 \(b_i\) 推到 \(b_{i+1}\)。即，我们需要找到 \((i,b_{i})\) 到 \(a\) 的凸壳的切线。由于 \(i\) 是递增的，且得到的 \(b\) 也是推的，所以切点是递增的，直接双指针即可。总复杂度 \(O(n)\)。
https://atcoder.jp/contests/arc130/submissions/50443191
标签：ARC130F,average,Replace,答案,凸壳,递增 From： https://www.cnblogs.com/TetrisCandy/p/18095817