大家好！我是小码匠。
今天分享的题目是标准的差分题目。
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：4道
- 待完成：296道
10/23～10/24
本周完成4道，后面2道稍后会进行分享
分类 | 算法 | 题目 |
|---|---|---|
算法基础 | 前缀和 | 【第001题】题解分享：湖南省选->激光炸弹 |
算法基础 | 差分 | 【第002题】题解分享：P4552 [Poetize6] IncDec Sequence |
前置知识
- 差分
题目地址
- https://www.luogu.com.cn/problem/P4552
题目描述
给定一个长度为 n 的数列
，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
输入格式
第一行一个正整数 n 接下来 n 行,每行一个整数,第 i 1行的整数表示
。
输出格式
第一行输出最少操作次数 第二行输出最终能得到多少种结果
输入输出样例
输入 #1复制
代码语言：javascript复制4
1
1
2
2
输出 #1复制
代码语言：javascript复制1
2
说明/提示
对于 100% 的数据，
。
题解
思路
- 思路可参照：https://www.luogu.com.cn/problem/solution/P4552
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
void best_coder() {
int n;
cin >> n;
vector<long long> a(n 1);
cin >> a[0];
long long z = 0, f = 0;
for (int i = 1; i < n; i) {
cin >> a[i];
long long x = a[i] - a[i - 1];
if (x > 0) {
z = x;
} else {
f = x;
}
}
f = abs(f);
cout << max(z, f) << 'n';
cout << max(z, f) - min(z, f) 1;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
END
