实际上这种操作区间使得数组到一个固定值（比如减少到全0）都可以用差分来做，而实际上的操作次数就是差分数组中正数的和，如果c[i]>0，表示需要在这段开始一个新的区间，所有c[i]>0的和，就是所有区间“起点”处的增量总和，也就是总的区间左端点选择次数。

不过在这里我们算差分数组前需要将a里面的元素统一减1，因为目标是全1不是全0，最后统计加和输出结果即可。

import sys
input = lambda:sys.stdin.readline().strip()

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
c=[0]*len(a)

for i in range(1,n+1):
    a[i] = a[i] - 1

for i in range(1,n+1):
    c[i] = a[i] - a[i-1]

ans=0
for i in c:
    if i>0:ans+=i
print(ans)

最精简的一集

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

ll n,m,k;

void solve()
{
	cin>>n;
	vector<ll>arr(n+1,1);
    ll ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
		if(arr[i]>arr[i-1])ans+=arr[i]-arr[i-1];
	}
	cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	ll T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

差分思想

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
#define ll long long
ll a[maxn];
ll d[maxn];
int n;
ll sum=0;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	d[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		
	}
	d[1]=a[1]-d[0];
	for(int i=2;i<=n;i++){
		d[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=n;i++){
		if(d[i]>0){
			sum+=d[i];
		}
	}
	cout<<sum<<endl;
	return 0;
}

import os
import sys
input = lambda:sys.stdin.readline().strip()
minput = lambda:map(int, input().split())
n = int(input())
a = minput()
prev = 1
d = []
for i in a:
    d.append(i - prev)
    prev = i
r = 0
t = [i for i in d if i > 0]
print(sum(t))

差分，注意ans开long long即可

#include <bits/stdc++.h>
using namespace std;
int diff[100005];
int a[100005];
typedef long long ll;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        a[i]-=1;
        diff[i]=a[i]-a[i-1];
    }
    //int ans=0;
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        if(diff[i]>0)ans+=diff[i];
    }
    cout<<ans;




    return 0;

}