岳阳网站定制,怎么给自己制作一个网站,云开发小程序源码,网站建设全程揭秘光盘文件题目描述
给定一个长度为 n 的数列 a_1,a_2,...,a_n#xff0c;每次可以选择一个区间[l,r]#xff0c;使这个区间内的数都加 1 或者都减 1。 请问至少需要多少次操作才能使数列中的所有数都一样#xff0c;并求出在保证最少次数的前提下#xff0c;最终得到的数列有多…题目描述
给定一个长度为 n 的数列 a_1,a_2,...,a_n每次可以选择一个区间[l,r]使这个区间内的数都加 1 或者都减 1。 请问至少需要多少次操作才能使数列中的所有数都一样并求出在保证最少次数的前提下最终得到的数列有多少种。
输入格式
第一行一个正整数 n 接下来 n 行,每行一个整数,第 i1 行的整数表示 a_i。
输出格式
第一行输出最少操作次数 第二行输出最终能得到多少种结果
样例 #1
样例输入 #1 4 1 1 2 2
样例输出 #1 1 2
提示
对于 100% 的数据n 100000, 0 a_i 2^31。 代码
#includeiostream
#includecstdio
#includealgorithm
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; // 程序结束
}
