自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 22:46:48，当前版本为作者最后更新于2023-04-27 20:22:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

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;
}