题解 – P4552 [Poetize6] IncDec Sequence

链接

小小绿题，其实我一开始思路还更对，结果开始的结论没推下去~

[Poetize6] IncDec Sequence

题目描述

给定一个长度为 n 的数列 {a_1,a_2,\cdots,a_n}，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 n
接下来 n 行,每行一个整数,第 i+1行的整数表示 a_i。

输出格式

第一行输出最少操作次数
第二行输出最终能得到多少种结果

样例 #1

样例输入 #1

4
1
1
2
2

样例输出 #1

1
2

提示

n\le 100000, 0 \le a_i \le 2^{31}。

题解

这个题一看就很简单对吧，我们只要维护一个差分，把原数组想象成一个台阶，然后应该轻松解决对吧？

来看图，理解一下到底该如何处理答案：

假设有这样一个数列，我们可以对任意一个区间进行加减1操作。对于不平的区间，也就是数都相等的区间，我们进行加减操作，区间还是不平的，所以两个区间之间的差已经需要被处理。

先进行演示：

在每步其实都可以把右边的降下来或者左边的升上去，该如何选择呢？其实可以发现，最优的选择方式就是只选择增加的这些数量，也就是差分为正的这些数，把它们加起来就是最终答案。

但是如果把这个台阶倒过来，再去看升高的台阶呢？

你会发现这边提升的数量明显更少，所以答案是不是就变小了呢？实际上不是。尝试想想只把增加的统计进答案，别的柱子还有很多高度都没更新，这怎么能对呢？

仔细想想，我们两次的处理是如何处理的。每次都把自己的高度同步给右侧的，也就是说每次最多让连续的一些递增台阶的高度相同，如果这个时候有递减的台阶，是无法同步的。所以可以得到表达式：

ans = min(p, q) + abs(p – q)

我们设有些阶梯要升高，有些阶梯要降低，会有一个要升高的最高的柱子，会有一个要降低的最低的柱子，这些柱子之间的都是第二问的答案。也可以将整个台阶看成一些递增台阶和一些递减台阶，去中和一个递增/递减的台阶，答案是显然的。

ans = abs(p – q)

写完了，自己感觉也很抽象，怎么办呢

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e5 + 10;
int n;
ll p, q;
vector<ll> a;
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  cin >> n;
  ll tmp, lst = 0;
  a.emplace_back(0);
  ll cnt1 = 0, mx = -1, mn = 0x3f3f3f3f3f3f3f3f;
  for(int i = 1; i <= n; i++) {
    cin >> tmp;
    a.emplace_back(tmp);
    if(i > 1) {
      cnt1 += abs_sub(a[i], a[i - 1]);
      if(a[i] - a[i - 1] > 0) p += a[i] - a[i - 1];
      else q -= a[i] - a[i - 1];}
  }
  cout << max(p, q) << endl;
  cout << max(p, q) - min(p, q) + 1 << endl;
  return 0;
}