【题目来源】
洛谷：[P4552 Poetize6] IncDec Sequence - 洛谷
【题目描述】
给定一个长度为 \(n\) 的数列 \({a_1,a_2,\cdots,a_n}\)，每次可以选择一个区间\([l,r]\)，使这个区间内的数都加 \(1\) 或者都减 \(1\)。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
【输入】
第一行一个正整数 \(n\)
接下来 \(n\) 行,每行一个整数,第 \(i+1\)行的整数表示 \(a_i\)。
【输出】
第一行输出最少操作次数
第二行输出最终能得到多少种结果
【输入样例】
4
1
1
2
2
【输出样例】
1
2
【解题思路】
【算法标签】
《洛谷 P4552 IncDec Sequence》 #差分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 数组长度
int a[100005]; // 原始数组
int b[100005]; // 差分数组
#define int long long // 定义int为long long类型signed 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];}int p = 0, q = 0; // p: 正差分和, q: 负差分和的绝对值// 计算正负差分和for (int i = 2; i <= n; i++) {if (b[i] > 0){p += b[i]; // 累加正差分}else{q += abs(b[i]); // 累加负差分的绝对值}}// 输出结果cout << max(p, q) << endl; // 输出最大操作次数cout << abs(p - q) + 1 << endl; // 输出可能的最终结果数return 0;
}
【运行结果】
4
1
1
2
2
1
2