题意

有n件货物,每件货物重 图片说明
每次操作可以让 区间 i ~ j 内的货物重量加一 或减一
求能让所有货物重量相等的最少操作次数

思路

这题能用差分数组求解 ,差分数组 图片说明

物品之间的重量相等那差分数组图片说明 全部为0

对于每次操作对区间 i ~ j 所有物品加一,差分数组 图片说明

对于每次操作对区间 i ~ j 所有物品减一 ,差分数组 图片说明

所以只要统计差分数组中正数之和和负数之和,取大的那个就好

为什么取大的那个? 假如差分数组为 a[i] = {1, -2, 3, 4},我们要让这个数组i >=2 && i <=4的数全部变为0 (数组设1为初始位置)

经过上面的分析要让数组中的两个数一个数 ++,另一个数 -- ;很显然我们先进行两次操作 a[2]+=2,a[3]-=2;

数组就变成了 {1,0,1,4} 当差分数组 i >= 2的值都为0时,图片说明 只是控制原数组的大小,所以jxnu 的这个数的值任取,所以我们下一步操作肯定是让 图片说明 的值全部变成 0;

所以有 a[1] += 1,a[3] -=1; a[1] += 4,a[4] -= 4; 总计操作了7次, 7 == 3(a[3]) + 4(a[4])。

代码

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1e5+5;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a[100005],b[100005];
int main(){
    int n = read();
    for(int i = 1 ; i <= n  ;++i){
        a[i] = read();
        b[i] = a[i] - a[i-1];
    }
    ll ans = 0,cnt = 0;
    for(int i = 2 ; i <= n ; ++i){
        if(b[i] > 0) ans += b[i];
        else cnt -= b[i];
    }
    cout<<max(ans,cnt)<<endl;
}