第十五届中北大学算法与程序设计竞赛 C

　　题意：现在给你n个数的数组，每次可以选择连续的区间操作，可以使得区间内每个数加1或者减去1。问最少多少次之后，可以使得整个数组变成相等的数。

　　题解：打出差分数组，如果差分数组从第二项开始为0。那么这就是一个相等的数组了。还有一点是，区间修改在差分数组中会变成两点的修改。例如修改([L,R])区间，例如加1，体现在差分数组上就是b[L]++,b[R+1]--。那么现在问题变成了，怎么把从差分数组第二项开始全变成0。我们考虑里面的所有正数和负数配对，然后可能会剩下一部分，只需要与1配对就可以了，稍加讨论可以得到最终答案。具体见代码：

　　#include

　　#define all(x) x.begin(),x.end()

　　#define fi first

　　#define sd second

　　#define lson (nd<<1)

　　#define rson (nd+nd+1)

　　#define PB push_back

　　#define mid (l+r>>1)

　　#define MP make_pair

　　#define SZ(x) (int)x.size()

　　using namespace std;

　　typedef long long LL;

　　typedef vector VI;

　　typedef pair PII;

　　inline int read(){

　　int res=0, f=1;char ch=getchar();

　　while(ch'9'){if(ch=='-')f=-1;ch=getchar();}

　　while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}

　　return res*f;

　　}

　　const int N = 200005;

　　const int MOD = 1000000007;

　　template

　　void chmin(T& a, T b){if(a>b)a=b;}

　　template

　　void chmax(T& a, T b){if(b>a)a=b;}

　　int n, a[N], b[N];

　　int main(){

　　n=read();

　　for(int i=1;i<=n;++i)a[i]=read();

　　for(int i=1;i<=n;++i)b[i]=a[i]-a[i-1];

　　LL p=0, q=0;

　　for(int i=2;i<=n;++i){

　　if(b[i]<0)p-=b[i];

　　else q+=b[i];

　　}

　　cout<

　　return 0;

　　}