Loading... 给定一个长度为 n 的数列 a1, a2, ..., an，每次可以选择一个区间 [l, r]，使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。 ### 输入格式 第一行输入正整数 n。 接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 ai。 ### 输出格式 第一行输出最少操作次数。 第二行输出最终能得到多少种结果。 ### 数据范围 * \$0 < n ≤ 10^5\$ * \$0 ≤ ai < 2^{31}\$ ### 输入样例 ``` 4 1 1 2 2 ``` ### 输出样例 ``` 1 2 ``` ### 题目分析 分析样例： 1 1 2 2 我们有两种最小增减结果： 1 1 1 1 2 2 2 2 我们可以获得 `1 1 2 2` 的差分数组 `1 0 1 0`。 可以发现，只要差分数组的第二位到最后一位都为`0`时，该序列的每个元素就完全相同。 根据上面的思路，我们可以先获得序列的差分数组。分别统计数组第二位之后的正数和`eve`和及负数和`neg`。 最小的操作步骤即 `max(eve, neg)`，能得到 `abs(eve - neg) + 1`种结果。 ### 代码实现 ``` #include <iostream> using namespace std; using ll = long long; const int N = 1e5 + 10; ll n, arr[N], val, eve, neg; inline void push(int l, int r, int val) { arr[l] += val, arr[r + 1] -= val; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) { cin >> val; push(i, i, val); } for (int i = 1; i < n; ++i) { if (arr[i] < 0) neg -= arr[i]; else eve += arr[i]; } cout << max(eve, neg) << '\n' << abs(eve - neg) + 1 << endl;; return 0; } ``` 最后修改：2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏