CF2018B题解

首先我们通过模拟一些样例可以得到一个贪心策略，那就是从城市j出发，每次扩展到当前未经过的ai最小的城市。这个策略是正确的。证明如下：设当前未经过的a值最小的城市为i，当前所占有的城市为[l,r]，当前未经过的除i以外的一个城市j。当i<l且j<l，无论我们决定先前往哪个城市，都可以接着往另一个城市扩展或顺带经过另一个城市，这一策略不会使得本来可以走到的城市扩展不到。i>r且j>r的情况同理。当i<l且j>r的时候，若我们先往j走，最后j和i都可以走到，那么j-r+1+t<=aj,l-i+1+t+j-r+1<=ai，此时先往i扩展也一定可以走到i和j，因为aj>=ai,j-r+1>0,所以l-i+1+t+j-r+1+t<=aj,l-i+1+t<=ai。i>r且j<l的情况同理。

有了这个策略还不够，直接运用这个策略模拟的时间复杂度太高了，所以我们需要一个运用这个策略的时间复杂度更低的方法。我们考虑对于每一个城市i，它能由哪些城市出发走到。我们会发现这些城市是一个连续的区间，最终的答案就是n个城市的区间的交区间的长度。那么接下来我们要做的就是求出每一个城市的区间。

找到满足aj<=ai的第一个和最后一个j，记为l,r,此时i∈[l,r]。若j<l，先向右走就是最优的，需要 i−j+1 步走到 i。能满足 i 的限制则意味着 i−j+1≤ai，即 j≥i−ai+1，[max(i−ai+1,1),l−1] 区间为可以走到i的城市的区间。若j>r，先向左走就是最优的，需要j-i+1步走到i。能满足i的限制则意味着j-i+1≤ai,即j≤ai+i-1,[r+1,min(i+ai-1,n)]区间为可以走到i的城市的区间。若l≤j<i，若 al≤ar，会先向左走到 l 然后拐个弯再向右走，需要 i−l+1 步走到 i，于是当 i−l+1≤ai时 [l,i−1] 区间为可以走到i的城市的区间；否则，直接向右走，类似地[max(i−ai+1,l),i−1] 区间为可以走到i的城市的区间。若i<j≤r ，若ar≤al,会先向右走到r然后拐个弯再向左走，需要r-i+1步走到i，于是当r-i+1≤ai时[i+1,r]区间为可以走到i的城市的区间。所以当r-i+1>ai或i-l+1>ai时没有任何一个城市能到达城市i。因为i∈[l,r]，所以上面这个判定等价于r-l+1>ai。除此之外，我们将以上几种情况的区间合并，得到的最终可以走到i的城市的区间就是[max(i-ai+1,1),min(i+ai-1,n)]。