题解 P6334 【[COCI2007-2008#1] SREDNJI】

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