题意：在做这道题前夕我们要懂得差分数组与前缀数组的关系。在之前我们应该知道，差分数组的影响对前缀数组的影响是，对于前缀数组[left,right]区间的值，我们要全部都加X，此时对于其的差分数组做的操作是b[left]+x,b[right+1]-x.因为a[i]=b[1]+b[2]+......+b[i].b[left]+x相当于a[left]之后的所有值都要加x，但是我们是在[left,right]区间内，所以我们要b[right+1]-x使得a[left]之后的值不变。对于这道题给出的三个操作，我们可以转化为差分数组的操作为：
(1)b[1]-1,b[i+1]+1
(2)b[i]-1,b[n+1]+1(这个时候n+1不存在，所以只有b[i]-1)
(3)b[1]+1.
思路:我们只需将差分数组全为0即可。用以上操作即可。关键我们要从i=2开始，最后如果b[1]不为0我们对他进行(2)或(3)操作即可。
代码如下：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll num1; cin>>num1; ll a[num1+1]; for(ll i=1;i<=num1;i++)cin>>a[i]; ll b[num1+1]; b[1]=a[1]; for(ll i=2;i<=num1;i++) { b[i]=a[i]-a[i-1]; } ll sum=0; for(ll i=2;i<=num1;i++) { if(b[i]<0) { sum+=abs(b[i]); b[1]-=abs(b[i]); b[i]=0; } else if(b[i]>0) { sum+=b[i]; b[i]=0; } } sum+=abs(b[1]); cout<<sum; }讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/91622.html