题解 – 波浪

大家好，欢迎来到IT知识分享网。

题目描述

在DOTA2第八届国际邀请赛（TI8）中，选手AME操刀的水人在关键时刻释放了一个波浪的技能，扭转局势，帮助OG战队获得冠军。
为了纪念这一技能，我们引出一个“波浪数组”的概念，其定义如下：
对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大。
例如[1,3,2,5,3,4]就是一个波浪数组，而[2,3,4,1,2]则不是，因为第二个位置3比左边的数字2大，比右边的数字4小。
注意：根据定义，长度小于等于2的数组一定是波浪数组。
现在有一个长度为n数组，你每次操作可以将任意一个位置的数字修改成任意一个新数字。我们想要将其变成一个波浪数组，请问最小的修改次数是几次？

输入

输出

对于每一组询问，输出一行一个整数表示最少修改次数。

样例

样例输入

【样例1】
6
1 1 2 2 3 3
【样例2】
11
703 702 703 703 702 703 702 702 702 700 702

样例输出

【样例1】
3
【样例2】
3

提示

样例1解释
可以将数组改为[1,5,2,4,1,3]或者[1,0,2,-1,5,3]等，都是波浪数组，其中加粗的数字表示被修改的数字。我们可以发现至少修改三个数字才可以将原来的数组变为波浪数组，所以答案为3。
【数据范围】
对于10%的数据，有1≤n≤20。
对于30%的数据，有1≤n≤1000。
对于另外10%的数据，有1≤n≤1e5，且数组元素各不相同。
对于另外10%的数据，有1≤n≤1e5，且数组元素全部相同。
对于100%的数据，有1≤n≤1e5,1≤ai≤1e9

分析

将数组变成波浪数组，最少的修改次数

将数组变成波浪数组，最少的修改次数

代码

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N =  + 10; int n; int a[N],b[N]; int mx = 1e9 + 1,mn = 0; int res = INT_MAX; int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin >> n; for(int i = 1;i <= n;i++){ cin >> a[i]; b[i] = a[i]; } if(n <= 2){ cout << 0; return 0; } int cnt = 0; for(int i = 2,op = 0;i <= n;i++,op = 1 - op){ if(op == 0){ if(a[i] >= a[i - 1]){ cnt++; a[i] = mn; } }else{ if(a[i] <= a[i - 1]){ cnt++; a[i] = mx; } } } res = min(res,cnt); cnt = 0; for(int i = 2,op = 1;i <= n;i++,op = 1 - op){ if(op == 0){ if(b[i] >= b[i - 1]){ cnt++; b[i] = mn; } }else{ if(b[i] <= b[i - 1]){ cnt++; b[i] = mx; } } } res = min(res,cnt); cout << res; return 0; }