题目描述

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

数据范围：n≤100000,1≤b≤n。

分析

显然n的值比较大，不能暴力。

那么思考一下对于中位数的处理。 中位数可以理解为左边比它大的数的数量与右边比它大的数的数量一样，也就是可以将数值简化为1与-1，即比它大与比它小。

然后通过前/后缀和来记录比它大或者小的数的数量情况，为0则是刚好满足中位数，-x则多了x个小的，+x则多了x个大的。

代码实现

那么读入的代码可以写成

int read()
{
    char ch ='\0';
    int sum = 0;
    while(ch<'0'||ch>'9') ch = getchar();
    while(ch>='0'&&ch<='9')
    {
        sum= sum*10 + (ch- '0');
        ch = getchar();
    }
    return sum;
}
int main()
{
    int n = 0, b = 0;
    scanf("%d %d",&n,&b);
    int s = 0;//记录中位数地址
    int a[100005] = {0};
    int x = 0;
    int cnt = 0;
    for(int i = 1;i<=n;i++)
    {
        x = read();
        if(x<b)a[i] = -1;
        else if(x>b)a[i] = 1;
        else s = i
    }
  //……
}

之后就是对数据进行处理，先是对s前面的数据求后缀和

    for(int i = s-1;i>=1;i--)
    {
        a[i] += a[i+1];
    }

再对s后面的数据求前缀和

同时遍历前面的数据，如果发现a[i]与a[j]的和为0，则为中位数

    for(int i = s;i<=n;i++)
    {
        if(i>s)a[i] += a[i-1];
        for(int j = s;j>=1;j--)
        {
            if(a[i]+a[j] == 0) cnt++;
        }
    }

最后输出即可。

但是超时了！

于是开始优化，首先是考虑只有左边和只有右边的情况，也就是前/后缀和为0时，可以直接cnt++。

其次，遍历前面，可以改为记忆当前数值有几个，空间换时间 ,使用st[]记忆。以s为中心，可以保证记录完整。

    int cnt = 0;
    int st[200005] = {0};
    st[s] = 1;//只往左时，记录差值为0时的情况有一种
    for(int i = s-1;i>=1;i--)
    {
        a[i] += a[i+1];//求后缀和
        if(a[i] == 0)cnt++;//只往前为0的情况
        st[s+a[i]]++;//记录
    }
    for(int i = s+1;i<=n;i++)
    {
        a[i] += a[i-1];//求前缀和
        cnt += st[s-a[i]];//加上和为0的情况有几种，因为前面st[s]至少有一个1，所以包含了只往后为0的情况
    }
    printf("%d",cnt+1);//最后加上只有b时的一种情况。

最后附上ac代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
    char ch ='\0';
    int sum = 0;
    while(ch<'0'||ch>'9') ch = getchar();
    while(ch>='0'&&ch<='9')
    {
        sum= sum*10 + (ch- '0');
        ch = getchar();
    }
    return sum;
}
int main()
{
    int n = 0, b = 0;
    scanf("%d %d",&n,&b);
    int s = 0;//记录中位数地址
    int a[100005] = {0};
    int x = 0;
    for(int i = 1;i<=n;i++)
    {
        x = read();
        if(x<b)a[i] = -1;
        else if(x>b)a[i] = 1;
        else s = i;
    }
    int cnt = 0;
    int st[100005] = {0};
    st[s] = 1;
    for(int i = s-1;i>=1;i--)
    {
        a[i] += a[i+1];
        if(a[i] == 0)cnt++;
        st[s+a[i]]++;
    }
    for(int i = s+1;i<=n;i++)
    {
        a[i] += a[i-1];
        cnt += st[s-a[i]];
    }
    printf("%d", cnt+1 );
    return 0;
}