本文主要是介绍BZOJ-3043 IncDec Sequence 差分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
100. IncDec序列
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行，每行输入一个整数，第i+1行的整数代表ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤10^5
0≤ai<2147483648
输入样例：
4
1
1
2
2
输出样例：
1
2
分析：
对于一个给定的数列A，它的差分数列B定义为,B[1] = A[1], B[i] = A[i] - A[i-1]（2<=i<=n）;.
我们可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。显然可得出公式：b[l]+=c,b[r+1]−=c，b[l]+=c, b[r+1]−=c 。
要使最后的数都一样，那么b2->bn一定全为0
全为0的话，a1=a2=a3=…=an
所以我们可以使用贪心的思想来做。差分第 1 项代表第一个数的大小，第 n+1 项代表第 n 个数的相反数，改变第1项或者第 n+1 项只会让数列整体变大或变小，并不影响数列相同。
计算差分序列，记录差分序列中正数和负数的个数。
区间内都加1/减1也就是对差分序列中区间两侧端点加一减一，每次可以让差分序列中的两个数一个+1，一个01
最佳情况是在差分序列中2-n项中任取一对正负数，每次就会消掉一个正数及一个负数。最多可以取min(正数，负数)次
差一些的情况是取2-n中的一个正数/负数，另一个取差分序列中的第1项或第n+1项，须进行abs(正数-负数)
如此，最小操作次数为min(正数，负数)+abs(正数-负数)
最终可能有多少种结果，只需要计算差分序列第一项或最后一项的可能结果。例如最后还剩3,那么有4种方案分别为(0,3),(1,2),(2,1),(3,0)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll a[maxn];
int main()
{ios::sync_with_stdio(false);int n;cin >> n;for(int i = 1; i <= n; i++) {cin >> a[i];}ll positive = 0, negative = 0;for(int i = n; i >= 2; i--) {a[i] = a[i] - a[i-1];if(a[i] > 0) {positive += a[i];} else {negative -= a[i];}}cout << min(positive, negative) + abs(positive - negative) << endl;cout << abs(positive-negative) +1 << endl;return 0;
}这篇关于BZOJ-3043 IncDec Sequence 差分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
