【思维】C港口（差分数组） 第十五届中北大学算法与程序设计竞赛

题目链接：https://ac.nowcoder.com/acm/problem/205919

题目描述：

港口有n堆货物，他们的重量分别为w1,w2,…wn，每堆货物的重量不一定相同。吊车师傅每次操作可以使任意第i堆到第j堆的货物都增加一个重量或者减少一个重量。请问吊车师傅最少需要执行几次操作可以使n堆货物重量都相同。

这个题是从差分数组的角度思考的。

1. 从差分数组的角度来看，每次对于区间[l,r]进行加操作就是对于差分数组cf[l]++,对cf[r+1]–;那么反过来思考，如果对原数组进行了区间[l,r]的加减操作，那么必然其差分数组一左一右分别进行了+1和-1的操作
2. 要使得原数组每个元素的大小都相同，即将该数组的差分数组的每一个元素（除第一个外）都变成0
3. 通过1和2两点，就把原题转化成了对差分数组的两点修改，所以最后我们只需求得怎么样可以在最小的改变次数下使得差分数组的所有值都为0
4. 题目所求是最小操作数，应用贪心的思路，我们只需输出差分数组中正数的和以及负数和的绝对值中的最大值即可

注意：第一个不算，即当差分数组为6,0,0,0,0时，已经满足了题目的条件

原因如下：当正数的绝对值大于负数的时候，至少需要进行正数的和次操作，这样才可以满足条件，而少的那一些负数的情况，可以是被其他大的区间给包括掉了，例如：当差分数组为1,4,-1，-1时，至少进行4次操作，因为至少要使得4变成0

代码：

#include <iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<sstream>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5+10;
ll w[maxn];
int n;
ll cf[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    cf[1]=w[1];
    for(int i=2;i<=n;i++)
        cf[i]=w[i]-w[i-1];//先处理出差分数组
    ll ans1=0;ll ans2=0;
    for(int i=2;i<=n;i++)
    {
        if(cf[i]>0) ans1+=cf[i];//只需算出加减的最大值即可
        else ans2+=-cf[i];
    }
    cout<<max(ans1,ans2)<<endl;
    return 0;
}