这个其实很好理解
假 如 a [ i ] < = a [ i + 1 ] , 那 我 们 不 需 要 对 a [ i + 1 ] 操 作 假如a[i]<=a[i+1],那我们不需要对a[i+1]操作 假如a[i]<=a[i+1],那我们不需要对a[i+1]操作
假 如 a [ i ] > = a [ i + 1 ] , 那 至 少 要 把 a [ i + 1 ] 加 到 a [ i ] 这 么 多 假如a[i]>=a[i+1],那至少要把a[i+1]加到a[i]这么多 假如a[i]>=a[i+1],那至少要把a[i+1]加到a[i]这么多
也 就 是 操 作 次 数 加 上 a [ i ] ? a [ i + 1 ] 也就是操作次数加上a[i]-a[i+1] 也就是操作次数加上a[i]?a[i+1]
可能你有疑惑,虽然 a [ i + 1 ] a[i+1] a[i+1]加到了和 a [ i ] a[i] a[i]一样多
但是不是前 i ? 1 i-1 i?1个元素最大的啊!!
nonono!
现在把 a [ i + 1 ] a[i+1] a[i+1]变得和 a [ i ] a[i] a[i]一样多, a [ i + 1 ] a[i+1] a[i+1]就可以和 a [ i ] a[i] a[i]一起操作
这样 a [ i ] a[i] a[i]变得大于等于 a [ i ? 1 ] a[i-1] a[i?1]的时候, a [ i + 1 ] a[i+1] a[i+1]也会跟着加
所 以 是 前 i + 1 个 元 素 最 大 的 了 所以是前i+1个元素最大的了 所以是前i+1个元素最大的了
给你这组样例去体会一下
【1392C - Omkar and Waterslide(思维)】6
8 1 7 1 1 1
#include
using namespace std;
#define int long long
const int maxn=2e5+10;
int a[maxn],n,t;
signed main()
{
cin >> t;
while( t-- )
{
cin >> n;
int ans=0;
for(int i=1;
i<=n;
i++) cin >> a[i];
for(int i=1;
i 
