第三个点死活过不去,求助一下dalao/kel
查看原帖
第三个点死活过不去,求助一下dalao/kel
198719
洛璟楼主2021/7/28 10:16

是wa了,将一个答案为1的点输出为0

#include<bits/stdc++.h>
using namespace std;
int t,n,a[300010],b[300010],ans,qwq;
int fg[300010];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		qwq=0;
		ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			fg[i]=0;
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		for(int i=2;i<n;++i)
		{
			if((a[i]<a[i-1] && a[i]<a[i+1]) || (a[i]>a[i+1] && a[i]>a[i-1]))//标记这个点是山峰或山谷
			{
				ans++;
				fg[i]=1;
			}
		}
		for(int i=2;i<n;++i)
		{
			int tmp=0;//记录最多可消去多少山峰/谷
			if((a[i]<a[i-1] && a[i]<a[i+1]) || (a[i]>a[i+1] && a[i]>a[i-1]))//如果这个是山峰或山谷
			{
				tmp++;
				b[i]=a[i-1];//枚举变成左边的点
				if(fg[i-1]==1)
				{
					tmp++;
				}
				if(fg[i+1]==1)//如果右边的点也是峰或谷
					if((b[i+1]<b[i] && b[i+1]<b[i+2]) || (b[i+1]>b[i+2] && b[i+1]>b[i]));
					else 
					{
						tmp++;
					}
				qwq=max(qwq,tmp);//记录答案
				tmp=1;//更新
				b[i]=a[i];
				b[i]=a[i+1];
				if(fg[i+1]==1)
				{
					tmp++;
				}
				if(fg[i-1]==1)
					if((b[i-1]<b[i-2] && b[i-1]<b[i]) || (b[i-1]>b[i] && b[i-1]>b[i-2]));				
					else 
					{
						tmp++;
					}
				qwq=max(qwq,tmp);
				b[i]=a[i];
			}
		}
		printf("%d\n",ans-qwq);
	}
	
	return 0;
}
2021/7/28 10:16
加载中...