【思維】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;
}