acwing--差分&&贪心

3道例题

5526. 平衡细菌 - AcWing题库

给一段区间上加上：1,2,3,4…^

则可构造区间的一阶差分（b[i]=a[i]-a[i-1]）：1,1,1,1……

再给上面的一阶差分序列进行一次差分，变成原序列的二阶差分（c[i]=b[i]-b[i-1]）：1,0,0,0……

如此一来，可以将原来区间一段的变化变为这个区间开头数字的变化。

我们可以看出原序列符合y=x的线性递增关系

而其一阶差分序列符合y=c的关系

而二阶差分序列则只有一个值的变化其余y=0

所以可拓展为将y=x^k变为y=0要进行k+1阶差分

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N],b[N],c[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];//一阶差分
    for(int i=1;i<=n;i++)c[i]=b[i]-b[i-1];//二阶差分
    int res=0;
    for(int i=1;i<=n;i++)res+=abs(c[i]);
    cout<<res<<endl;
    return 0;
}

507. 积木大赛 - AcWing题库 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int res=0;
    for(int i=n;i>=1;i--)res+=max(0ll,a[i]-a[i-1]);//反着来，因为如果正着来的话，减之前数组值会发生变化
    cout<<res<<endl;
    return 0;
}

531. 铺设道路 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int res=0;
    for(int i=n;i>=1;i--)res+=max(0ll,a[i]-a[i-1]);//有贪心可知，如果下陷程度小于上一块则可填
    cout<<res<<endl;
    return 0;
}