看错题后不小心加强了.jpg

· · 题解

最开始看成坐标减一要消耗燃料了

发现是坐标减一不要钱。

以下定义坐标加为往右走。

那么最优策略一定是形如一开始一直往右走，走到某个点停下往左走，选定沿途的一些基地卖鱼。

显然右左右左这种走法是不优的。

所以考虑枚举走到的最右侧的地方，设为 X，那么可以把一些鱼收集起来，然后选择的基地的价格显然是一段后缀。

若所有基地可出售重量和小于等于可收集鱼的重量和，就能卖就卖。

否则就二分出最长的价格后缀 [x,10^6] 使重量之和小于等于可收集鱼的重量和，还有剩的卖给价格为 x-1 的基地即可。

以上操作可以用树状数组实现。

枚举 X 显然只需枚举特殊点即可。