洛谷：P3406：海底高铁

题目

P3406：海底高铁

分析

这道题需要想清楚两个点。假定A是单程票的价格，C是充值卡的费用（一次性），B是买了卡后的优惠价格。

1. 两个物理相邻站点的旅行（城市1-城市2）是直接买票便宜，还是买充值卡后享受折扣便宜，完全取决于要旅行的次数（count）。\(count\times B+C \le count\times A\)的时候，充值卡便宜。
2. A-B的旅行，需要经过A和B之间所有的站点。所以，如果从3-1，那么必须经过2号站点，反之亦然。因此，看到诸如1-4这样的路线，我们需要有1-2/2-3/3-4三次旅行。也就是1/2/3三个站点都要出发一次到下个物理相邻的站点。

这种区间集体增加一个数值的操作，当然可以用暴力法，但用差分数组更方便。

令\(P[i]\)表示从i号城市出发到i+1号城市的差分数组。要修改[i, j]之间所有城市的经过次数，我们只要：\(diff[i]+1, diff[j]-1\)即可。然后再用差分反求原始数组的方式，得到各个站点的出发次数：\(count[i]=count[i-1]+diff[i]\)。特别规定\(diff[0]=0\)，因为0号城市不存在，也就不存在从那里出发的列车。

显然，这个差分操作，将原来M个（站点）可能跨度N（站点总数）的操作（\(M\times N\))，降到了\(M\times 2\)次。通过差分还原原来的\(count\)时，也只要最多进行\(N\)次操作。所以总的时间复杂度从\(O(M\times N)\))降到了\(O(M+N)\)。

答案

思考

（略）