Hills And Valleys CodeForces - 1467B

題意：

修改數列中的 一個 數字 使得峰(波峰、波谷)的數量最少

題解：

修改一個數，最多只能影響左右兩個數，所能減少的峰的數量為1,2，3三種
分類討論，對于當前位置i，如果我們將a[i]變成比左右兩邊都小的情況，比左右兩邊都大的情況，位于兩者中間的情況，等于左邊的情況，等于右邊的情況，以上所有情況均取最大的到temp
然后用總數量減去temp

代碼:

#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; #define int long long int t, n, a[maxn]; int judge(int i) {if (i >= 2 && i <= n - 1) {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; } signed main() {cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int ans = 0, temp = 0;for (int i = 2; i <= n - 1; i++)if (judge(i)) ans++;for (int i = 1; i <= n; i++) {int now = judge(i - 1) + judge(i + 1) + judge(i);int last = 1e9;int f = a[i];a[i] = min(a[i - 1], a[i + 1]) - 1; //比小的小last = min(last, judge(i - 1) + judge(i + 1) + judge(i));a[i] = max(a[i - 1], a[i + 1]) + 1; //比大的大last = min(last, judge(i - 1) + judge(i + 1) + judge(i));a[i] = min(a[i - 1], a[i + 1]) + 1; //位于中間last = min(last, judge(i - 1) + judge(i + 1) + judge(i));a[i] = a[i - 1]; //相等last = min(last, judge(i - 1) + judge(i + 1) + judge(i));a[i] = a[i + 1]; //相等last = min(last, judge(i - 1) + judge(i + 1) + judge(i));temp = max(temp, now - last);a[i] = f;}cout << ans - temp << endl;} }

總結

以上是生活随笔為你收集整理的Hills And Valleys CodeForces - 1467B的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。