Educational Codeforces Round 105 (Rated for Div. 2)C
题目
一维坐标上有n个箱子ai,还有m个特殊位置bi。你刚开始位于位置0,你可以推箱子,不能翻越、拉箱子。问你最多可以把多少个箱子推到特殊位置。
刚开始位于坐标0,正负半轴对称,因此只需考虑一边,另一边同理。
以正半轴为例,我们只能往正方向推动箱子,且这个状态不可逆。那么我们必然存在POS,使得人走到位置POS(沿途将箱子往前推)得到最优解。贪心的思考一下,我们必须会把推动的连续个箱子的终止位置(即最右边那个箱子)控制在某个bi。因此只需要枚举结束位置bi即可。
代码
1 | /* |