CF1987C Basil's Garden 题解

壹·题目描述

有 $n$ 个数字排成一排，接下来每隔一秒进行一次操作：
如果 $i=n$ 或 $h_i>h_{i+1}$，则第 $i$ 盆花的高度 $h_i$ 将变为 $\max(0,h_i-1)$。请问至少经过多少秒后，所有的数字都为$0$。

贰·思路分析

可以知道，$h_i \leq 1$时$h_i←0$。显然可以换个思路，倒推分析，有公式:
$$A_i←max{(A_i+1,h_i)}$$
那么需要花费$a_{i+1}+1$或$i$秒的时间。

贰·代码实现

#include<bits/stdc++.h>
using namespace std;
int n,t,a[1e5+10],k;//定义大一点，空间OK的 

int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)//一共t组数据，故循环输入，并处理数据 
    {
    	k=0;
		cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];//输入 
        for(int i=1;i<=n;i++) k=max(a[i]+i,k);//公式处理 
        cout<<k-1<<endl;//注意不是k 
	}
    return 0;
}
//很短的