题解：P12662 [KOI 2023 Round 2] 滑冰练习

· · 题解

解题思路

考虑贪心。

因为对于某个点的限速 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;
}