给定一个长度为 n n n 的数列 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an，每次可以选择一个区间 [ l , r ] [l,r] [l,r]，使下标在这个区间内的数都加一或者都减一
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种
输入格式
第一行输入正整数 n n n
接下来 n n n 行，每行输入一个整数，第 i + 1 i+1 i+1 行的整数代表 a i a_i ai
输出格式
第一行输出最少操作次数
第二行输出最终能得到多少种结果
数据范围
0 < n ≤ 105 0 < n \leq 105 0<n≤105
0 ≤ a i < 2147483648 0 \leq a_i < 2147483648 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 3 = a 3 − a 2 . . . b n = a n − a n − 1 这样所有数一样就转化为让 b 2 ∼ b n = 0 ， b 1 任选，最后整个序列就由 b 1 决定 问题转化为： ①至少操作多少次，可以使 b 2 ∼ b n = 0 ②在操作次数最小的情况下， b 1 由多少种取值 a L ∼ a R 加上 1 经由差分序列可以转化为 b L + = 1 , b R + 1 − = 1 目标是让 b 2 ∼ b n = 0 , b 1 和 b n + 1 随意，故将所有操作按对 b 的影响分为 4 类： ① 2 ≤ L ≤ R ≤ n − 1 ：在 b 2 ∼ b n 中令某一个数加 1 另外一个数减 1 ② L = 1 , R ≤ n − 1 ： b 1 加 1 ， b 2 ∼ b n 中的某个数减 1 ； b 1 减 1 ， b 2 ∼ b n 中的某个数加 1 ③ 2 ≤ L , R = n ： b n + 1 加 1 ， b 2 ∼ b n 中的某个数减 1 ； b n + 1 减 1 ， b 2 ∼ b n 中的某个数加 1 ④ L = 1 , R = n ：无意义 因为①操作可以改变两个 b 2 ∼ b n 的数，故应该优先使用 设所有的正数之和为 p ，负数的绝对值之和为 q ，先使用①操作 m i n { p , q } 次，剩余 ∣ p − q ∣ 次用②或③操作 故总共需要操作的次数为 m i n { p , q } + ∣ p − q ∣ = m a x { p , q } 对于剩下的 ∣ p − q ∣ 个数，可以选②或者③，②操作会改变 b 1 ③操作不会改变 因而总共不同的个分配方案有 ∣ p − q ∣ + 1 个 对一个序列同时加一减一，有一个非常常用的方式就是差分\\ 一个序列：a_1,\ a_2\ ...\ a_n，构造其差分序列\\ b_1=a_1\\ b_2=a_2-a_1\\ b_3=a_3-a_2\\ ...\\ b_n=a_n-a_{n-1}\\ 这样所有数一样就转化为让b_2\sim b_n=0，b_1任选，最后整个序列就由b_1决定\\ 问题转化为：\\ ①至少操作多少次，可以使b_2\sim b_n=0\\ ②在操作次数最小的情况下，b_1由多少种取值\\ a_L \sim a_R加上1经由差分序列可以转化为b_L+=1,\ b_{R+1}-=1\\ 目标是让b_2\sim b_n=0,\ b_1和b_{n+1}随意，故将所有操作按对b的影响分为4类：\\ ①2\leq L\leq R\leq n-1：在b_2 \sim b_n中令某一个数加1另外一个数减1\\ ②L=1,\ R\leq n-1：b_1加1，b_2 \sim b_n中的某个数减1；b_1减1，b_2 \sim b_n中的某个数加1\\ ③2\leq L,\ R=n：b_{n+1}加1，b_2 \sim b_n中的某个数减1；b_{n+1}减1，b_2 \sim b_n中的某个数加1\\ ④L=1,\ R=n：无意义\\ 因为①操作可以改变两个b_2 \sim b_n的数，故应该优先使用\\ 设所有的正数之和为p，负数的绝对值之和为q，先使用①操作min\{p,q\}次，剩余|p-q|次用②或③操作\\ 故总共需要操作的次数为min\{p,q\}+|p-q|=max\{p, q\}\\ 对于剩下的|p-q|个数，可以选②或者③，②操作会改变b_1③操作不会改变\\ 因而总共不同的个分配方案有|p-q|+1个 对一个序列同时加一减一，有一个非常常用的方式就是差分一个序列：a1, a2 ... an，构造其差分序列b1=a1b2=a2−a1b3=a3−a2...bn=an−an−1这样所有数一样就转化为让b2∼bn=0，b1任选，最后整个序列就由b1决定问题转化为：①至少操作多少次，可以使b2∼bn=0②在操作次数最小的情况下，b1由多少种取值aL∼aR加上1经由差分序列可以转化为bL+=1, bR+1−=1目标是让b2∼bn=0, b1和bn+1随意，故将所有操作按对b的影响分为4类：①2≤L≤R≤n−1：在b2∼bn中令某一个数加1另外一个数减1②L=1, R≤n−1：b1加1，b2∼bn中的某个数减1；b1减1，b2∼bn中的某个数加1③2≤L, R=n：bn+1加1，b2∼bn中的某个数减1；bn+1减1，b2∼bn中的某个数加1④L=1, R=n：无意义因为①操作可以改变两个b2∼bn的数，故应该优先使用设所有的正数之和为p，负数的绝对值之和为q，先使用①操作min{p,q}次，剩余∣p−q∣次用②或③操作故总共需要操作的次数为min{p,q}+∣p−q∣=max{p,q}对于剩下的∣p−q∣个数，可以选②或者③，②操作会改变b1③操作不会改变因而总共不同的个分配方案有∣p−q∣+1个
②代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N], b[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n + 1; i++)
b[i] = a[i] - a[i - 1];
long long p = 0, q = 0;
for (int i = 2; i < n + 1; i++)
if (b[i] > 0)
p += b[i];
else
q += abs(b[i]);
printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
return 0;
}
③细节分析
构造差分数组
for (int i = 1; i <= n + 1; i++) // 因为要用到i-1，故下标从1开始 b[i] = a[i] - a[i - 1]; // a[i] = b[1]+...+b[i]利用上面推导出来的结论，只需要关心 b 2 ∼ b n b_2 \sim b_n b2∼bn
long long p = 0, q = 0; for (int i = 2; i < n + 1; i++) if (b[i] > 0) p += b[i]; else q += abs(b[i]);