自动搬运

查看原文

来自洛谷，原作者为

	wyhm **

搬运于2025-08-24 22:19:46，当前版本为作者最后更新于2020-08-30 16:33:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

这道题目我们可以使用前缀和做，我们记录这些数，比 $b$ 小的记做 $-1$，比它大的记做 $1$，相等的记做 $0$，然后双重循环暴力枚举可能的方案，只有 $90$ 分。

#include <stdio.h>
int x[100001],ans,s,n,b;
int main() 
{
	scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
		scanf("%d",&s);
		x[i]=x[i-1]+(s>b?1:-1)+(s==b);
    }
    for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=2)
			ans+=(x[j]-x[i-1]==0);
    printf("%d",ans);
    return 0;
}

优化：

上面那个代码明显是可以优化的，我们只要 $x$ 相等，而且位置相差是偶数，方案就可以满足要求。如果是现在循环到了一个偶数位置，那么就把答案加上记录奇数出现个数的数组，然后记录偶数出现的加上 $1$，否则做法相反。

代码：

#include <stdio.h>
int x[200001],y[200001],ans,a,n,b,s;
int main() 
{
	scanf("%d%d",&n,&b);
	y[n]=1;//这里考虑负数，所以n就代表零了，赋初始值
    for(int i=1;i<=n;i++)
    {
		scanf("%d",&a);
		s=s+(a>b?1:-1)+(a==b);//判断，如果相等前面部分会将它减一所以还要判断，加回去
		if(i%2==0)//上面解释了做法
			ans+=x[n+s],y[n+s]++;
		else 
			x[n+s]++,ans+=y[n+s];
    }
    printf("%d",ans);
    return 0;
}