公司创建网站销售,重庆本地生活平台,可以自己免费做的软件,网站如何做链接Hills And Valleys CodeForces - 1467B
题意#xff1a;
修改数列中的 一个 数字 使得峰(波峰、波谷)的数量最少
题解#xff1a;
修改一个数#xff0c;最多只能影响左右两个数#xff0c;所能减少的峰的数量为1,2#xff0c;3三种 分类讨论#xff0c;对于当前位置…Hills And Valleys CodeForces - 1467B
题意
修改数列中的 一个 数字 使得峰(波峰、波谷)的数量最少
题解
修改一个数最多只能影响左右两个数所能减少的峰的数量为1,23三种 分类讨论对于当前位置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;}
}
