链接

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

[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;
}