Median on Segments (Permutations Edition)

124 阅读 0 评论 82 点赞

我是靠谱客的博主和谐长颈鹿，这篇文章主要介绍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:

Input2:

5 5
1 2 3 4 5

Output2:

Input3:

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

Output3:

样例说明：

样例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：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

区间优化：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：题解
浏览次数：124 次浏览
发布日期：2023-08-21 16:30:19
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_18_fz_13_zgy.html

Median on Segments (Permutations Edition)