Hills And Valleys
题意
修改数列中的 一个 数字 使得峰(波峰、波谷)的数量最少
思路
首先我们通过手写几个例子可以知道 修改一个数只能影响到左右两个数 所以能减少的峰的数量为 1、2、3 三种情况
其次 若将这个数修改成 两边两个数构成的范围之外 那么不会改变峰的数量 所以第i个数的改变范围为 [ a i − 1 , a i + 1 ] 可以贪心地将其改成左边的数计算出能减少多少个峰 再将其变成右边的数 计算出能减少多少个峰 结果取max 即可
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 300010; int n; int a[N]; int check(int i) { if (i == 1 || i == n)return 0; if (a[i] < a[i - 1] && a[i] < a[i + 1])return 1; if (a[i] > a[i - 1] && a[i] > a[i + 1])return 1; return 0; } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } int cnt = 0; for (int i = 2; i <= n - 1; ++i) { if (check(i))cnt++; } int res = 0; for (int i = 2; i <= n - 1; ++i) { if (check(i) == 1) { //是峰 int t1 = check(i - 1) + check(i) + check(i + 1); int inita = a[i]; a[i] = a[i - 1]; int res1 = check(i - 1) + check(i) + check(i + 1); a[i] = a[i + 1]; int res2 = check(i - 1) + check(i) + check(i + 1); res = max(res, t1 - min(res1, res2)); a[i] = inita; } } //cout << "cnt == " << cnt << endl; //cout << "res == " << res << endl; cout << cnt - res << endl; } int main() { int t; cin >> t; while(t--) solve(); return 0; }
