P15034 [UOI 2021 II Stage] 奇迹之地 题解

· · 题解

题目传送门：P15034 [UOI 2021 II Stage] 奇迹之地

题目分析

对于一个数 x，如果我们要把它砍掉，那一定要砍成 1。因为能砍它意味着前面没有比它大的，所以砍多少都无所谓，最多能砍 x-1。

考虑分析什么时候不能砍。根据上面的分析，在 x 之前没有大于等于它的数，那只有 x-1 能挡住它。所以只要前面存在不能被砍的 x-1，那这个 x 就是不能被砍的。

归纳地，存在不能被砍的 x-1 代表前面存在不能被砍的 x-2……而所有的 1 是不能被砍的。

因此只需记录“不能被砍”叠到了多少层。记 x 不能被砍的充要条件是小于等于 y，如果 x=y 则令 y \leftarrow y+1，否则如果 x > y 就将 x 砍为 1，并将贡献加入答案。

:::warning[注意] 若 y=1，将 x 砍为 1 后也会令 y 自增。 :::

此外答案要开 long long。

代码实现

#include<iostream>
using namespace std;
int n,x,y=1;
long long ans;
int main(){
    cin>>n;
    while(n--){
        cin>>x;
        if(x>y)ans+=x-1,x=1;
        if(x==y)y++;
    }
    cout<<ans;
    return 0;
}

AC 记录。