Link

CF1901 B Chip and Ribbon

Qustion

初始有 \(n\) 个格子，刚开始每个格子都是 \(0\) ，Monocarp 刚开始在一号格子中，并使得 \(a[1]+1\)，每一轮，Monocarp 可以进行两个操作

操作 1 ，Monocarp 移动到下一个格子，
操作 2 ，Monocarp 移动到任意一个格子

每一轮结束，Monocarp 所在的格子 \(+1\)

给出每个格子的最终值 \(a_i\) ，问最少需要做几次操作 2

Solution

我们发现，

\(a_{i-1}<a_{i}\) 时，必须要执行操作 2 ，执行操作 2 的次数是 \(a_i-a_{i-1}\) ，
\(a_{i-1}>a_i\) 时，可以通过操作 1 把 \(a_{i-1}\) 的值 "传递" 到 \(a_i\)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans=0;
const int maxn=2e5+5;
int a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void solve(){
    int N=read();ans=0;
    for(int i=1;i<=N;i++) a[i]=read();
    a[0]=1;
    for(int i=1;i<=N;i++){
        if(a[i-1]<a[i]) ans+=a[i]-a[i-1];
    }
    printf("%lld\n",ans);
}
int main(){
    // freopen("B.in","r",stdin);
    int T=read();
    while(T--)solve();
}