郑州微网站,河源网站优化,十大战略咨询公司,科技无国界P4552 [Poetize6] IncDec Sequence - 洛谷 | 计算机科学教育新生态
题目描述
给定一个长度为 n 的数列 a1,a2,…,an#xff0c;每次可以选择一个区间 [l,r]#xff0c;使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样#…P4552 [Poetize6] IncDec Sequence - 洛谷 | 计算机科学教育新生态
题目描述
给定一个长度为 n 的数列 a1,a2,…,an每次可以选择一个区间 [l,r]使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样并求出在保证最少次数的前提下最终得到的数列有多少种。
输入格式
第一行一个正整数 n接下来 n 行每行一个整数第 i1 行的整数表示 ai
输出格式
第一行输出最少操作次数第二行输出最终能得到多少种结果
输入输出样例
输入 #1
4
1
1
2
2
输出 #1
1
2
说明/提示
对于 100% 的数据n≤1000000≤ai≤2的31次方。
思路 代码如下
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
typedef long long ll;
const ll N 1e510;
ll arr[N];
ll pre[N];
ll n;
ll p,ne;
int main()
{cin n;for(ll i 1 ; i n ; i){cin arr[i];pre[i] arr[i] - arr[i-1];}for(ll i 2 ; i n ; i){if(pre[i] 0)p pre[i];else if(pre[i] 0)ne - pre[i];}cout max(p,ne) endl;cout max(p,ne) - min(p,ne) 1;return 0;
}
