题目

Problem - 1700C - Codeforces

题意

​ 给一个数组，存在以下三种操作，

• （1）将数组中 $a_1\sim a_i$ 的数减一。
• （2）将数组中 $a_i\sim a_n$ 的数减一。
• （3）将数组中全部数加一。

​ 求将数组全部数字变为 0 的最小操作数。

使用差分数组，将原数组变为全零转化为将差分数组变为全零。可以将原来的操作进行转化。

• （1）$b_1-1$，$b_i+1$。
• （2）$b_i-1$。
• （3）$b_1+1$。

所以，发现只有操作（1）能对除 1 以外的数字加一，只有操作（2）能对除 1 以外位置减一，所以只需要对差分数组除 1 以外的位置进行处理，最后用（2）（3）操作判断位置 1 就可以。

注意要开 long long。

#include <iostream>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll T,a[N],b[N];
void slove(){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];ll ans=0;for(int i=2;i<=n;i++){if(b[i]>0)ans+=b[i];else if(b[i]<0){ans-=b[i];b[1]+=b[i];}}cout<<ans+abs(b[1])<<endl;
}
int main(){cin>>T;while(T--)slove();return 0;
}