CQOI2009中位数图

[CQOI2009]中位数图

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

题目描述

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

输入描述:

第一行为两个正整数n和b ，第二行为1~n 的排列。

输出描述:

输出一个整数，即中位数为b的连续子序列个数。

输入

7 4
5 7 2 4 3 1 6

输出

4

思路1：（大佬直接跳到思路4即可）纯暴力，对于中位数，我们肯定知道对于一个序列（排好序后），以中位数x为分界线，左边比x小的数和右边比x大的数个数相同，直接的想法就是暴力枚举每一种可能的区间，判断b是否在区间以及是否满足排好序后(暴力的话大可不必排序这个区间，只需枚举区间中比b大的个数和比b小的个数即可)小的和大的一样多，这种方法时间复杂度O（n^3）

#include<iostream>
using namespace std;
const int N=1e5+5;
int a[N],ans;
bool judge(int i,int j,int t)
{
    int minx=0,max=0;
    for(int k=i;k<=j;k++)
    {
        if(a[k]>a[t])
        max++;
        else if(a[k]<a[t])
        minx++;
    }
    return minx==max;
}
int main()
{
    int n,x,t;
    scanf("%d%d",&n,&x);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==x)t=i;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        if(i<=t&&t<=j&&judge(i,j,t))
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}
//通过50%

思路2：优美暴力

我们在此方法上对O（n^3）进行优化，我们是不是可以对这个排列预处理，也就是求前缀和，对于minx[i]表示前i个数中比b小的个数，maxx[i]表示前i个数中比b大的个数，那么我们只用两层循环就可以了O（n^2）。

#include<iostream>
using namespace std;
const int N=1e5+5;
int a[N],ans,minx[N],maxx[N];
int main()
{
    int n,x,t;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==x)t=i;
    }
    for(int i=1;i<=n;i++)//预处理过程基本上就是核心了
    {
        if(a[i]<a[t])minx[i]++;
        else if(a[i]>a[t])maxx[i]++;

        minx[i]+=minx[i-1];
        maxx[i]+=maxx[i-1];

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        if(i<=t&&j>=t&&(minx[j]-minx[i-1])==(maxx[j]-maxx[i-1]))
        {
            ans++;
            //printf("%d %d\n",i,j);
        }
    }
//    for(int i=1;i<=n;i++)
//    printf("%d %d\n",minx[i],maxx[i]);
    printf("%d\n",ans);
    return 0;
}
//ac80%

思路3：也就是最优解，对于某个区间{L,R}
中位数b：左边
--L小：表示在b左边比b小的个数
--L大：表示在b左边比b大的个数
中位数b：右边
--R小：表示在b右边比b小的个数
--R大：表示在b右边比b大的个数
上述条件满足：L小+R小=L大+R大，变换一下：L小-L大=R大-R小=j
只要存在L小-L大=R大-R小就说明这段区间{L，R}满足条件，接下来我们枚举从b开始到n的区间，求前缀和，maxx[i]和minx[i],并且统计cnt[maxx[i]-minx[i]=j]++，也就是这个j的数量，这里用map统计即可（因为考虑到可能存在负值情况，或者在统计值j的时候+n防止越界），上述过程就是在从b右边开始统计j的数量，那么我们是不是再从b左边开始求minx[i]-maxx[i]=j的值（注意这里和变换那里条件要一样），统计这个j值的数量是不是就是对答案的贡献，当然在枚举做区间时，要记得res=cnt[0],这种情况要先被加进去（因为=0的情况已经符合条件了，不懂得模拟一下即可）。最后输出res即可

#include<iostream>
#include<map>
using namespace std;
const int N=1e5+5;
int a[N],ans,minx[N],maxx[N];
map<int,int>m;
int main()
{
    int n,x,t;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==x)t=i;//找到这个位置
    }
    for(int i=t;i<=n;i++)//右端点前缀和处理
    {
        if(a[i]<a[t])minx[i]++;
        else if(a[i]>a[t])maxx[i]++;
        minx[i]+=minx[i-1];
        maxx[i]+=maxx[i-1];
        m[maxx[i]-minx[i]]++;//这里就是我们要找的R大-R小得个数key（maxx[i]-minx[i]）代表上述思路的j
    }
    ans=m[0];//一开始在右端点就已经有满足的了，因为j=0,就代表大于和小于的个数相等
    for(int i=t-1;i>=1;i--)//枚举左端点，这里一定是从左端点末尾开始，因为要用前缀和处理，从小到大开始处理不了i到x的大于和小于个数
    {
        if(a[i]<a[t])minx[i]++;
        else if(a[i]>a[t])maxx[i]++;
        minx[i]+=minx[i+1];
        maxx[i]+=maxx[i+1];
        ans+=m[minx[i]-maxx[i]];//这里就是我们要找的L小-L大=j看有多少个和R大-R小=j相等而通过key就直接能找到相等的个数
    }
    printf("%d\n",ans);
    return 0;
}
//AC

思路4：对思路3的优化，我们直接让这个区间中比b大的=1，比b小的=-1，那么直接用sum对右区间求前缀和，同时统计值的数量（这里看到其他的题解都是在统计的前把cnt[N]=1,然后又在统计过程中把cnt[0]贡献到答案中，而我是从b的位置开始统计相当于cnt[N]=1,然后统计完值，将res=cnt[N]了，根据个人喜好把，理解即可），然后对左区间进行求后缀和，同时贡献答案

#include<iostream>

using namespace std;
const int N=1e5+5;
int a[N],cnt[N<<1];//N<<1防止N过于大造成段错误（因为自己发生数组越界了QAQ）
int main()
{
    int n,b,pos;
    cin>>n>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>b)a[i]=1;
        else if(a[i]<b)a[i]=-1;
        else if(a[i]==b)a[i]=0,pos=i;
    }
    int sum=0;
    for(int i=pos;i<=n;i++)
    {
        sum+=a[i];
        cnt[sum+n]++;
    }
    int res=0;
    res=cnt[n],sum=0;
    for(int i=pos-1;i>=1;i--)
    {
        sum+=a[i];
        res+=cnt[n-sum];
    }
    cout<<res<<endl;
    return 0;
}

//ac

总结：思路4大部分就是题解区的操作了，细节部分只需要注意一下，本身中位数b(也就是cnt[0+n])就是对答案的一种贡献，题解区都是将cnt[n]=1,直接这样统计到答案里边，这里我是把a[i]==b时，a[i]=0，然后直接从pos位置枚举，也把它统计到答案里边了，另外在有区间还有cnt[0+n]的情况也需要统计到答案里边，最后只需res=cnt[n]即可，然后去枚举左区间就行了。（写这篇题解是因为在之前遇到过这道题，然后在这里碰到了，就是换了种说法，又发现不会了...）

换种说法的传送门：传送门