[CH0304]IncDec Sequence

和NOIP2018DAY1T1类似的题目，但思维难度高多了。

这题既可以抬高路面，也可以降低路面，而且目标平面不确定，就难起来了。

但是两道题的基本思路几乎一样，同样我们将 2~n 的高度差分，1之所以不要差分是因为最终的高度是不确定的。

所以现在的目标就是将这个差分数组的任意一个位置 +1/-1 ，另一个位置 -1/+1，使 2~n 的差分数组变成 0，显然最少次数就是 max(正数之和，负数绝对值之和) 。

第二问要求最终的可能平面有多少种，考虑操作的过程中当正的或负的已经被搞成 0 ，只剩一部分负的或正的，那这对应原来的数组就是从 2~n 单调的，所以1的取值只能在最高点和最低点之间，这样才能保证次数最少，答案就是 abs(正数之和 - 负数绝对值之和) + 1

#include <set>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <assert.h>

#include <algorithm>

using namespace std;

#define LL long long

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define GO debug("GO\n")

inline int rint() {

  register int x = 0, f = 1; register char c;

  while (!isdigit(c = getchar())) if (c == '-') f = -1;

  while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

  return x * f;

}

template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; }

template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }

#define int LL

signed main() {

#ifndef ONLINE_JUDGE

  freopen("xhc.in", "r", stdin);

  freopen("xhc.out", "w", stdout);

#endif

  int n;

  cin >> n;

  int x = 0, y = 0, last, now;

  cin >> last;

  for (int i = 2; i <= n; ++ i) {

    cin >> now;

    if (now > last) y += now - last;

    else x += last - now;

    last = now;

  }

  cout << max(x, y) << endl << abs(y - x) + 1 << endl;

  return 0;

}

巴特西

[CH0304]IncDec Sequence

最新文章

热门文章