Acwing -100 IncDec序列 (差分+贪心)

给定一个长度为 nn 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数n。

接下来n行，每行输入一个整数，第i+1行的整数代表ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0<n≤1050
0≤ai<2147483648.

输入样例：

4
1
1
2
2

输出样例：

1
2

 

题解:  这里涉及到了差分的性质以及贪心 , 再来回顾一下差分数组 ,  比如有一个数组 a[1] , a[2] .... a[n] ; 

差分数组就是 b[1] = a[1] , b[2] = a[2] -a[1] ..... b[n] = b[n] - b[n-1] ,  并且 a[1] = 1 , a[2] = b[1] +b[2] , a[n] = b[1] +b[2] ...b[n] .

也就是 a 数组是b数组的前缀和 , b 数组是a 数组的差分数组。

差分数组的一个性质就是, 对原数组a 在区间 [ L ,R ] 上同时加上一个常数 C ,就等价于 对b数组(a的差分数组) , b[L]+=C , B[R+1]-=C ; 具体见  https://blog.csdn.net/qq_41661809/article/details/86727017 . 

这个题目, 是要我们对原数组,选择一个区间, 然后将区间加一或者减一的操作使得原数组所有的元素变成一样的, 而且用最少的操作数 , 我们可以等价的对它的差分数组进行操作 .   因为要使得原数组全一样不就是让他的差分数组全变为0 ,所以我们就等价的对差分数组进行操作,从而降低复杂度.  这个题就是说,我们在差分数组中任意的选择两个端点,进行加一和减一操作,使得差分数组变成0 , 所以我们要使操组数变少,可以每次将一个正数减一,将一个负数加一,这样就可以更快的趋近0 (ps : 这里是正数和负数是一个配对操作), 但是差分数组中 sum(正数) 可能不等于sum(负数)  , 比如现在只剩下正数了, 我们固定左端点为i = 1 ,右端点为  2<= j <=n ,进行操作, 最后达到全为0 ;  

#include <iostream>
#include <algorithm>
#include <cstdio>
#pragma GCC optimize(2)
#include <cmath>
#define pi 3.141592654
using namespace std ;
const int MAX = 100010 ;
typedef long long LL ;
int a[MAX] ;
int main(){
   int n ;
   cin >>n;
   for(int i = 1; i<=n ; i++ )cin>> a[i] ;
   for(int i = n;i>1 ; i--) a[i]-=a[i-1] ;
   LL pos = 0 , neg = 0 ;
   for(int i = 2 ; i<=n ; i++) {
   	if(a[i]>0 ) pos+=a[i] ;
   	else neg -=a[i] ;
   }
   // pos 为差分数组中的正数之和 , neg 为差分数组中的负数之和
   cout<<min(pos,neg) + abs(pos-neg)<<endl ;
   cout<<abs(pos-neg)+1 <<endl;
   

	return 0 ;
}