题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3043
题意：
给定一个长度为n的数列a[i]，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
求：（1）至少需要多少次操作才能使数列中的所有数都一样。
（2）在保证最少次数的前提下，最终得到的数列有多少种。
题解：
对于差分来说，给[l,r]+1（或-1）就是给差分数组s[l]+1和s[r+1]-1。
所以数列a[i]，是从一个所有元素都相等的初始数组，经过若干次差分操作得来的。
因此可以求出a[i]的差分数组s[i]。
因为要使操作次数最小，所以先让s[i]中的正数和负数配对（可能有剩余），每一对"+1"和"-1"对应一次操作。
剩下来的正数（或负数），只能单独消去。
pos为s[i]的正数之和，neg为s[i]的负数的绝对值之和。
所以第（1）问的答案为max(pos,neg)。
因为要使操作次数最小，所以配对的"+1"和"-1"一定会被消去，对于最终数列的种类没有影响。
所以只用考虑剩下来的正数（或负数）的消去方法。
对于一个在i位置的"+1"来说，有两种消去方法：
（1）自己跟自己消，即在s[i]再-1。
从效果上看，相当于给a[i]及后面的数都-1。
（2）跟位置1消，即在s[i]处-1。
相当于给[1,i]之间的数-1。
对于这两种消去方法，最终数组的数字大小相差1。
剩下的数共有abs(pos-neg)个。
所以最终数组的数字大小最多相差abs(pos-neg)，即数字种类有abs(pos-neg)+1种。
abs(pos-neg)+1即为第（2）问答案。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005 using namespace std; int n;
long long pos=;
long long neg=;
long long a[MAX_N]; long long labs(long long x)
{
return x>?x:-x;
} void read()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
} void solve()
{
for(int i=;i<n;i++)
{
if(a[i]>a[i-]) pos+=a[i]-a[i-];
else neg+=a[i-]-a[i];
}
} void print()
{
cout<<max(pos,neg)<<endl;
cout<<labs(pos-neg)+<<endl;
} int main()
{
read();
solve();
print();
}