题目链接

P9253 [PA 2022] Ornitolog 2

题目简述

给定一个音高序列，输出最少要修改多少整数才能使这个序列成为交替鹡鸰鸟鸣的音高序列。

题意分析

操作后的音高序列总共有 \(2\) 种可能：

1. 音量由高变低再由低变高；

2. 音量由低变高再由高变低。

又因为大小范围是 \(10^4 \times 5\)，因此将数组开大一点定义大小为 \(10^5+10\)。

这样也需要考虑 \(2\) 种情况：

1. 如果 \(i\) 为偶数，且 \(a_{i-1} \le a_{i}\)，那么将对应的 \(sum\) 增加 \(1\)，将 \(pd\) 设为 true；

2. 如果 \(i\) 为奇数，且 \(a_{i-1} \le a_{i}\)，那么将对应的 \(sum\) 增加 \(1\)，将 \(pd\) 设为 true，否则将 \(pd\) 设为 false。

最后只需要输出两种情况所需要的操作次数的最小值即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define QwQ return 0;
int a[100010],n,sum1,sum2,pd;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++)//首先考虑第一种情况
	{
		if(i%2==0)
		{
			if(a[i-1]>=a[i]&&pd==0)
				sum1++,pd=1;
			else
				pd=0;
		}
		else
		{
			if(a[i-1]<=a[i]&&pd==0)
	         	sum1++,pd=1;
			else//否则将pd设为0
				pd=0;
		}
	}
	pd=0;
	for(int i=1;i<n;i++)//然后再考虑第二种题目
	{
		if(i%2==1)//如果i为奇数，且a[i]>=a[i-1]那么sum2增加1，将pd设为 1
		{
			if(a[i-1]>=a[i]&&pd==0)
				sum2++,pd=1;
			else//否则将pd设为0
				pd=0;
		}
		else//如果i为偶数，且a[i]>=a[i-1]那么sum2增加1，将pd设为1
		{
			if(a[i-1]<=a[i]&&pd==0)
				sum2++,pd=1;
			else//否则将pd设为 0
				pd=0;
		}
	}
	cout<<min(sum1,sum2);//输出最小值
   QwQ;
}