第3个点第217组数据死活过不去,求助/kel(有注释
查看原帖
第3个点第217组数据死活过不去,求助/kel(有注释
156353
GoldenFishX楼主2021/3/9 20:25
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 5;

int a[MAXN];
bool f[MAXN];
int ans, n;

int check(int i, int x) { //求把第i个改成x会减少多少
  int ans = f[i - 1] + f[i + 1] + f[i], cnt = 0;
  cnt += (i - 2 >= 1 && (a[i - 2] > a[i - 1] && x > a[i - 1]) || (a[i - 2] < a[i - 1] && x < a[i - 1]));  //前一个
  cnt += (a[i - 1] > x && a[i + 1] > x) || (a[i - 1] < x && a[i + 1] < x);                                //自己
  cnt += (i + 2 <= n && (x > a[i + 1] && a[i + 2] > a[i + 1]) || (x < a[i + 1] && a[i + 2] < a[i + 1]));  //后一个
  ans -= cnt;
  return ans;
}

int Find() {
  int maxx = f[1] || f[n]; //如果头或尾有峰谷,那么显然可以消掉其中一个
  for (int i = 2; i < n; i++) {
    maxx = max(maxx, check(i, a[i - 1]));
    maxx = max(maxx, check(i, a[i + 1]));
  }
  return maxx;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      f[i] = 0;
    }
    for (int i = 2; i < n; i++) {
      if ((a[i - 1] > a[i] && a[i + 1] > a[i]) || (a[i - 1] < a[i] && a[i + 1] < a[i])) { //这个是不是峰谷
        f[i] = 1;
        ans++;
      }
    }
    ans -= Find();
    cout << ans << endl;
  }
  return 0;
}
2021/3/9 20:25
加载中...