Median on Segments (Permutations Edition)

Median on Segments (Permutations Edition)

题目大意：

给定一个长度为n的数列{p1,p2,…,pn}由{1,2,…,0}组成。
求满足中位数为m的闭区间[l,r]的个数。
（当区间内元素为偶，中位数取中间靠左的那个数）

输入格式：

n m
p1 p2 p3 … pn

输出格式：

count

样例输入输出：

Input1:

5 4
2 4 5 3 1

Output1:

4

Input2:

5 5
1 2 3 4 5

Output2:

1

Input3:

15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9

Output3:

48

样例说明：

样例1：中位数为4，有[1,3],[2,2],[2,3],[2,4]。
样例2：中位数为5，有[5,5]。
样例3：数据稍大，不能样例分析，但可以用来判错。

简单、题解：

由给定的中位数出发，可以得到一些性质。
1. [l,r]包含m
2. [l,r]满足题意时，[l,r]内，小于m的数=大于m的数(区间元素个数为偶时+1)

令m在数列中的位置为p
令c[i]为[i,p](或 [p,i])中小于m的数与大于m的数的差值（可为负）。
则： 区间[l,r]的中位数是m<=>c[l]+c[r]==0或-1。

最终转化问题为：
在[1,p]中选一个x，在[p,n]中选一个y，使得c[x]+c[y]==0或-1

准备了两种方法：
Map 和 区间优化

参考程序：

Map：

#include<cstdio>
#include<map>
using namespace std;
#define MAXN 200000

int n,m,p;
long long ans;
int c[MAXN+5];
map<int,int>Map;

int main() {
    scanf("%d %d",&n,&m);
    int i,a;
    for(i=1;i<=n;i++) {
        scanf("%d",&a);
        if(a==m)
            p=i;
        else if(a<m)
            c[i]=1;
        else c[i]=-1;
    }
    Map[c[p]]++;//m点不能掉
    for(i=p-1;i>=1;i--) {
        c[i]+=c[i+1];
        Map[c[i]]++;
    }
    ans+=Map[-c[p]]+Map[-c[p]-1];//m点不能掉
    for(i=p+1;i<=n;i++) {
        c[i]+=c[i-1];
        ans+=Map[-c[i]]+Map[-c[i]-1];
    }
    printf("%lldn",ans);
    return 0;
}

区间优化：

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200000

int n,m,p;
long long ans;
int c[MAXN+5];

int main() {
    scanf("%d %d",&n,&m);
    int i,a;
    for(i=1;i<=n;i++) {
        scanf("%d",&a);
        if(a==m)
            p=i,i++,n++;
        else if(a<m)
            c[i]=1;
        else c[i]=-1;
    }
    for(i=p-2;i>=1;i--)
        c[i]+=c[i+1];
    for(i=p+3;i<=n;i++)
        c[i]+=c[i-1];
    sort(c+1,c+p+1);//优化
    sort(c+p+1,c+n+1);
    int l=n,r=n;//l是虚点
    for(i=1;i<=p;i++) {
        while(c[i]+c[l]>=-1&&l>p)
            l--;
        while(c[i]+c[r]>0&&r>p)
            r--;
        ans+=r-l;
    }
    printf("%lldn",ans);
    return 0;
}

最后

以上就是和谐长颈鹿为你收集整理的Median on Segments (Permutations Edition)的全部内容，希望文章能够帮你解决Median on Segments (Permutations Edition)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。