南宁市建设信息网站短链接生成器

题目描述

给定一个长度为 n 的数列 a_1,a_2,...,a_n，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。 
  
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 n   
接下来 n 行,每行一个整数,第 i+1 行的整数表示 a_i。

输出格式

第一行输出最少操作次数   
第二行输出最终能得到多少种结果

样例 #1

样例输入 #1
4
1
1
2
2

样例输出 #1
1
2

提示

对于 100% 的数据，n<= 100000, 0 <= a_i <= 2^31。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;  // 定义 long long 类型的别名为 LL
LL n, c, p, q, a[100010];  // 声明变量int main()
{cin >> n;  // 输入数组的长度 nfor (int i = 1; i <= n; i++){scanf("%lld", &a[i]);  // 输入数组的元素}for (int i = 2; i <= n; i++)  // 从第二个元素开始遍历数组{c = a[i] - a[i - 1];  // 计算相邻元素之间的差值if (c > 0)  // 如果差值大于 0，说明需要增加操作{p += c;  // 累加增加操作次数}else  // 否则，需要减少操作{q -= c;  // 取反后累加减少操作次数}}LL ans1 = max(p, q);  // 找到增加和减少操作次数中的较大值，作为最少操作次数LL ans2 = abs(p - q) + 1;  // 计算操作次数之差的绝对值加 1，作为最终可能的结果种数cout << ans1 << endl << ans2;  // 输出最少操作次数和结果种数return 0;  // 程序结束
}