題目描述 Description
給定一個長度為n的數列{a1,a2...an}，每次可以選擇一個區間[l,r]，使這個區間内的數都加一或者都減一。
問至少需要多少次操作才能使數列中的所有數都一樣,并求出在保證最少次數的前提下,最終得到的數列有多少種。
輸入描述 Input Description
第一行一個正整數n
接下來n行,每行一個整數,第i+1行的整數表示ai。
輸出描述 Output Description
第一行輸出最少操作次數
第二行輸出最終能得到多少種結果
樣例輸入 Sample Input
4
1
1
2
2
樣例輸出 Sample Output
1
2
資料範圍及提示 Data Size & Hint
對于100%的資料，n=100000，0<=ai<2147483648。
/*
典型的差分題目
先做一個差分序列b，接下來就是怎麼把除了b1之外的所有數都變成0，因為可以進行區間修改，那麼對于序列b來說就是一個數加1的同時一個數減1，或一個數加1，或一個數減1。因為要求步數最少，是以要盡可能把加1用在負數上，把減1用在正數上，剩下的隻有正數或負數時再單獨加1或減1。至于方案數，取決于b1，那麼我們要在不影響步數的情況下修改b1，那麼隻能把單獨加1或減1換成修改b1和原來那個數。
*/
#include<cstdio>
#include<iostream>
#define M 100010
#define ll long long
using namespace std;
ll a[M],b[M];int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]-a[i-1];
}
ll tot1=0,tot2=0;
for(int i=2;i<=n;i++)
if(b[i]>0)tot1+=b[i];
else tot2-=b[i];
cout<<max(tot1,tot2)<<endl<<max(tot1-tot2,tot2-tot1)+1;
return 0;
} View Code
轉載于:https://www.cnblogs.com/harden/p/5924953.html