花都定制型网站建设,建筑工人找活正规平台,济南seo优化公司助力网站腾飞,seo学习网站题目
给定一个长度为 n 的数列 a1,a2,…,an#xff0c;每次可以选择一个区间 [l,r]#xff0c;使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样#xff0c;并求出在保证最少次数的前提下#xff0c;最终得到的数列可能有多少种…题目
给定一个长度为 n 的数列 a1,a2,…,an每次可以选择一个区间 [l,r]使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样并求出在保证最少次数的前提下最终得到的数列可能有多少种。
输入格式
第一行输入正整数 n。
接下来 n 行每行输入一个整数第 i1 行的整数代表 ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0 n ≤ 1e5 0 ≤ ai 2147483648
输入样例
4
1
1
2
2输出样例
1
2思路
假设我们有一个序列9 8 7 10 11 12 4 5 第一步我们先求出差分数组然后使得差分数组的值为0第一位不需要变 sum1 abs(所有负数之和)
sum2 所有正数之和
sum1 与 sum2 均与差分数组第一位无关
将差分数组除第一位全部变为0需要操作 max(sum1,sum2)次
差分数组的第一位的取值个数ans max(sum1,sum2) - min(sum1,sum2) 1;
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N 1e5 10;
int n;
int a[N],b[N];
int p,q;int32_t main()
{cin n;for(int i 1; i n; i ) cin a[i];for(int i 1; i n; i ) b[i] a[i] - a[i - 1];for(int i 2; i n; i ){if(b[i] 0) p b[i];else q - b[i];}cout max(p,q) endl;cout abs(p - q) 1 endl;return 0;
}
题目来自 100. 增减序列 - AcWing题库
难度中等时/空限制1s / 64MB总通过数16399总尝试数35129来源《算法竞赛进阶指南》算法标签
题目来自100. 增减序列 - AcWing题库
