问个问题,关于昨天CF的B
  • 板块学术版
  • 楼主5ab_juruo
  • 当前回复12
  • 已保存回复12
  • 发布时间2021/1/9 07:47
  • 上次更新2023/11/5 05:01:20
查看原帖
问个问题,关于昨天CF的B
119491
5ab_juruo楼主2021/1/9 07:47

rt,昨天打 CF 时的题,交了好几发都在第三个点 WA,好像是有些测试点多减了一个 1。看了官方题解和代码,感觉上没有区别,但还是 WA 了一样的点,求助。

#include <cstdio>
#include <cctype>
using namespace std;

const int max_n = 300000;
int a[max_n], incs[max_n] = {}, n;

#define gc getchar
inline int read()
{
	int c = gc(), t = 1, n = 0;
	while (isspace(c)) { c = gc(); }
	if (c == '-') { t = -1, c = gc(); }
	while (isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

inline int my_min(int u, int v) { return (u < v)? u:v; }

inline int incx(int i)
{
	if (i == 0 || i == n-1)
		return 0;
	
	return ((a[i-1] < a[i] && a[i] > a[i+1]) || (a[i-1] > a[i] && a[i] < a[i+1]));
}

int main()
{
	int cas = read(), iv, ta, ti, ans;

	while (cas--)
	{
		iv = ans = 0;

		n = read();
		for (int i = 0; i < n; i++)
			a[i] = read();
		
		for (int i = 1; i < n-1; i++)
			iv += (incs[i] = incx(i));
		
	//	fprintf(stderr, "%d\n", iv);

		if (n >= 3)
		{
			ans = iv;

			for (int i = 1; i < n-1; i++)
			{
				ta = a[i];

				a[i] = a[i-1];
				ans = my_min(ans, iv - incs[i-1] - incs[i] - incs[i+1] + incx(i-1) + incx(i) + incx(i+1));
				
				a[i] = a[i+1];
				ans = my_min(ans, iv - incs[i-1] - incs[i] - incs[i+1] + incx(i-1) + incx(i) + incx(i+1));
				
				a[i] = ta;
			}
		}

		printf("%d\n", ans);
	}

	return 0;
}
2021/1/9 07:47
加载中...