题目描述
给定一个长度为 n 的数列 a1,a2,…,an,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数 n。
接下来 n 行,每行输入一个整数,第 i+1 行的整数代表 ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤105,
0≤ai<2147483648
样例
输入样例:
4
1
1
2
2
输出样例:
1
2
Java 代码
import java.util.*;
public class Main{
// 什么是差分数组?假设数组为A,差分数组为B,则原数组A_i为B_i的前i项和
// 比如A={1,1,2,2},则B={1,0,1,0}(假设下标从1开始,下标0处给默认值0)
// 因为B[i] = A[i] - A[i - 1] -->A[i] = B[1] + B[2] + ... + B[i](i >= 1)
// 如果要使得A={2,2,2,2},需要A[1]和A[2]都加上1
// 对于B则需要B[1]+1,B[3]-1,即B={2,0,0,0}
// 观察上述可得出要让A在[l,r]区间上全部进行加/减1,则需要在B[l]加/减1,B[r+1]上减/加1
// B[l]加/减1的目的:
// A[l + 2] = B[1] + B[2] + ... B[l]* + B[l + 1] + B[l + 2]中因为B[l]加/减1,其他没变
// B[r+1]减/加1的目的:
// A[r + 1] = B[1] + B[2] + ... B[l]* + ... + B[r] + B[r + 1]*中因为B[l]加/减1,为了不影响区间外的数,B[r + 1]减/加1
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] nums = new int[n];
for (int i = 0; i < n; i ++)
{
nums[i] = sc.nextInt();
}
// 计算差分数组
int [] f = new int[n];
f[0] = nums[0];
for (int i = 1; i < n; i ++)
{
f[i] = nums[i] - nums[i - 1];
}
long a = 0L;
long b = 0L;
for (int i = 1; i < n; i ++)
{
if (f[i] > 0)
{
a += f[i];
}
else
{
b += (-f[i]);
}
}
long min_op = Math.min(a, b) + Math.abs(a - b);
long op_cnt = Math.abs(a - b) + 1;
System.out.println(min_op);
System.out.println(op_cnt);
}
}