https://ac.nowcoder.com/acm/problem/19913

题目描述
给出1-n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。
输入描述:
第一行为两个正整数n和b ,第二行为1~n 的排列。
输出描述:
输出一个整数,即中位数为b的连续子序列个数。
示例1
输入

7 4
5 7 2 4 3 1 6

输出

4

根据排列的特点,序列中只有一个b,我们可以以b为标准0,把其他数字表示成-1,1;
以题目样例为例:
5 7 2 4 3 1 6
即:1 1 -1 0 -1 -1 1
表示成这样以后,长度为奇数的连续子序列,就是区间和为0的连续子序列。区间和的求法,一种方法是前缀和。
之后以b为中心向右求前缀和,向左求后缀和。
在这里,笔者是分为了三种情况讨论:
【1】连续子序列全部位于b位置的左边,遍历查看0的个数;
【2】连续子序列全部位于b位置的右边,遍历查看0的个数;
【3】连续子序列跨越了b,位于b的左右两边,所以我写了个暴力的两重循环。

#include <bits/stdc++.h>
#include <cstdio>
//#define local
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+5;
const int inf = 0x3f3f3f3f;
int n,b,a[N],pos;
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
#endif // local
    scanf("%d%d",&n,&b);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==b)
            a[i]=0,pos=i;
        else if(a[i]>b)
            a[i]=1;
        else
            a[i]=-1;
    }
    for(int i=pos;i>1;i--)
        a[i-1]+=a[i];
    for(int i=pos;i<n;i++)
        a[i+1]+=a[i];
//    for(int i=1;i<=n;i++)
//        printf("%d ",a[i]);
    int ans=0;
    for(int i=0; i<pos; i+=2)//左边,i+=2,保证长度为奇数,从0开始是因为b一个数时也合法
        if(a[pos-i]==0)
            ans++;
    for(int i=2; i<=n-pos; i+=2)//右边,
        if(a[pos+i]==0)
            ans++;
    for(int i=pos+1;i<=n;i++)//左右两边
    {
        for(int j=1;j<pos;j++)
        {
            if(a[i]+a[j]==0)
                ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}