自动搬运

查看原文

来自洛谷，原作者为

	tanruiqing 非绿名以下的用户兹磁壶关（2025.7.24前和我壶关的免），壶关请私||最后在线时间：2025年8月24日23时16分

搬运于2025-08-24 23:17:12，当前版本为作者最后更新于2025-06-01 11:45:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

考虑贪心。

因为对于某个点的限速 $v_i$，我们应该在合法的情况下会以 $v_i$ 的速度经过这个点而不是用 $1\sim v_i-1$ 的速度经过这个点。不然我们就无法最大化练习成果的值。

但是，这里有不合法的情况，所以我们需要修改其中的某些值来让整个序列符合要求。

考虑从前往后推。

就用样例二来解释。

4
23 7 1 5

最开始，我们会看到数字 $23$，它比前一个数字（起点）$0$ 大，所以合法。

然后，我们会看到数字 $7$，它比前面一个数字 $23$ 小，所以我们需要修改数字 $23$ 为 $8$，这样才能满足条件“每次只能从上一个经过的中间点的速度减少 1”。

接着，我们会看到数字 $1$，它比前面的数字 $7$ 小，所以要修改数字 $7$ 的值为 $2$，但是，这样还没有合法，因为第一个数字 $8$ 比第二个数字 $2$ 大，所以要将数字 $8$ 改为 $3$，这样才合法。

后面依此类推……

这里我们可以发现，每一次更改都要从前往后检查一次序列，所以时间复杂度为 $\varTheta(n^{2})$，而 $n$ 的数据范围有 $500000$，显然会超时。

考虑从后往前推。

还是用样例二来解释。

4
23 7 1 5

最开始，我们会看到数字 $5$，它比后一个数字（终点） $0$ 大，所以要将其改为 $1$，这要才能满足条件“最后以速度 0 到达终点后结束”。

然后，我们会看到数字 $1$，它比后面一个数字 $1$ 一样，所以合法。

接着，我们会看到数字 $7$，它比后面的数字 $1$ 大，所以要修改数字 $7$ 的值为 $2$，这样才合法。

后面依此类推……

这里我们可以发现，每一次更改都不影响前面的值，所以这里的时间复杂度为 $\varTheta(n)$，可以通过。

AC 代码

AC 记录。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;

int a[500005];

int ans;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //输入。
    if(a[n]>1)a[n]=1;//如果终点前一个到达的点的速度不为1，就要将其更改为1。因为最后题目说“最后以速度 0 到达终点后结束。”，而且“每次只能从上一个经过的中间点的速度减少 1。”，所以最后一个点的限速因改为1。
    for(int i=n-1;i>=1;i--){
        //从后往前推。
        if(a[i]>a[i+1]+1){
            //如果现在这一个点的速度大于上一个点的速度+1，就无法将速度降下来，所以更改其值为a[i+1]+1。
            a[i]=a[i+1]+1;
        }
    }
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    //最后累加答案。
    cout<<ans;//输出。
    return 0;
}