1467B. Hills And Valleys(思维模拟)

传送门

先扫一遍求出原有的威胁度

然后直接枚举每一个数来改变,取能减小威胁的最大值即可

比如 a   b   c a\ b\ c a b c

现在要改变 b b b,无非 5 5 5种可能

b b b m i n ( a , c ) min(a,c) min(a,c)还小

b b b等于 m i n ( a , c ) min(a,c) min(a,c)

b b b介于 m i n ( a , c ) min(a,c) min(a,c) m a x ( a , c ) max(a,c) max(a,c)之间

b b b等于 m a x ( a , c ) max(a,c) max(a,c)

b b b m a x ( a , c ) max(a,c) max(a,c)还大

这五种可能已经涵盖了所有的大小关系

而威胁度之和相对大小关系有关,所以这么做不会漏掉任何答案

#include bits/stdc++.h
using namespace std;
const int maxn = 3e5+10;
#define int long long
int t,n,a[maxn];
int is(int i)
{
	if( i=2i=n-1 )
	{
		if( a[i]a[i+1]a[i]a[i-1] )	return 1;
		if( a[i]a[i+1]a[i]a[i-1] )	return 1;
	}
	return 0;
}
signed main()
{
	cin  t;
	while( t-- )
	{
		cin  n;
		for(int i=1;i=n;i++)	cin  a[i];
		int ans = 0,temp = 0;
		for(int i=2;i=n-1;i++)	if( is(i) )	ans++;
		for(int i=1;i=n;i++)
		{
			int now = is(i-1)+is(i+1)+is(i),last=1e9,f = a[i];
			a[i] = min( a[i-1],a[i+1] )-1;//比小的小 
			last = min( last,is(i-1)+is(i+1)+is(i) );
			a[i] = max( a[i-1],a[i+1] )+1;//比大的大 
			last = min( last,is(i-1)+is(i+1)+is(i) );
			a[i] = min( a[i-1],a[i+1] )+1;//位于中间 
			last = min( last,is(i-1)+is(i+1)+is(i) );
			a[i] = a[i-1];//相等 
			last = min( last,is(i-1)+is(i+1)+is(i) );
			a[i] = a[i+1];//相等 
			last = min( last,is(i-1)+is(i+1)+is(i) );
			temp = max( temp,now-last );
			a[i] = f;
		}
		cout  ans-temp  endl;
	}
}
最新回复(0)
/jishuc_2FznfhawZxBh1ALwE5ZnIr6luhIRHxDGZ4Y8qLK8V1U_3D4834427
8 简首页