插分 贪心

这道题主要是在一段数组，问我们最小操作数，我们只有一种操作，就是从l-r使我们数组（数组名是s）s[l]-s[r]全部-1，所以我想到了能O（1）修改区间的插分

样例 4 3 2 5 3 5

差分 0 4 -1 -1 3 -2 2

插分修改区间l到r - 1是

s[l]-1

s[r+1]-1

我们最终是把数组操作成全0

0 0 0 0 0 0 0

因为我们前i个数前缀和是道路深度，一定大于等于0，所以插分数组一个负数左边一定有正数，让我们进行刚才的插分操作，我们整个前缀和大于等于0，所以最后会只剩下正数或0，如果只剩下正数那么操作时，r=n，也就是s[n+1]-1；不过可以不管，超出插分数组了，所以我们算左端操作比较简单

问题就转化成插分数组正数的和

插分不多赘述

    for(int i=n;i>=1;i--) s[i]=s[i]-s[i-1];

ac程序 时间复杂度O（N） 空间复杂度O（N）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;

int n;
int s[N];
int ans;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=n;i>=1;i--) s[i]=s[i]-s[i-1];
    for(int i=1;i<=n;i++){
        if(s[i]>0) ans+=s[i];
    }
    cout<<ans;
    return 0;
}