【C++】波浪

问题 D: 波浪

时间限制: 1.000 Sec  内存限制: 128 MB
提交 状态

题目描述

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

输入

输入第一行包含一个正整数n，代表数组长度。
接下来一行包含n个正整数，其中第i个数字表示数组的第i个元素ai。

输出

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

样例输入 Copy

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

样例输出 Copy

【样例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≤10^5，且数组元素各不相同。
对于另外10%的数据，有1≤n≤10^5，且数组元素全部相同。
对于100%的数据，有1≤n≤10^5,1≤ai≤10^9

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], mn, mx = 1e9 + 1, res = INT_MAX;
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d",&a[i]);
		b[i] = a[i];
	}
	if(n <= 2) 
	{
		puts("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 << '\n';
	return 0;
}