Codeforces Round #496 E1. Median on Segments (Permutations Edition)(思路)

136 阅读 0 评论 90 点赞

我是靠谱客的博主明理小伙，这篇文章主要介绍Codeforces Round #496 E1. Median on Segments (Permutations Edition)(思路)，现在分享给大家，希望可以做个参考。

题意
给你一个n和m，问你这样一组序列(从1到n)中有多少个子序列是以m为中位数的，如果这个序列长度是偶数，那么就取中间偏左的那个数字
思路
百度之星原题：
HDU5701
和百度之星唯一不同的就是

如果这个序列长度是偶数，那么就取中间偏左的那个数字

仔细想一下，如果我们对于当前的数，我往左，往右延申比他大的我++，比他小的我–，之后如果有某个时刻这个和是0了，那么是不是就说明m是这个区间的一个中位数。
代码

复制代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int a[maxn*2],vis[maxn*2];
int main()
{
    int n,m;
    int pos = 0;
    scanf("%d%d",&n,&m);
    for(int i = 0 ; i < n ;i ++)
    {
        scanf("%d",&a[i]);
        if(a[i] == m)
        {
            pos = i;
        }
    }
    int cnt = 0;
    for(int i = pos ; i < n ; i++)
    {
        if(a[i] > m) cnt++;
        if(a[i] < m) cnt--;
        vis[maxn + cnt] ++; // 当前指的 maxn + cnt 指的是，比m大的值和比m小的值的差，通俗的讲就是我现在还差 -cnt 个可以凑到0 
    }
    cnt = 0;
    long long ans = 0;
    for(int i = pos ; i >= 0 ; i--)
    {
        if(a[i] < m) cnt ++;
        if(a[i] > m) cnt --;
        ans += vis[maxn + cnt]; // 这个就是 我现在已经凑到 cnt个了，那么他的值就是0，于是就有vis[cnt]个区间了 
        ans += vis[maxn + cnt + 1]; // 仔细想想就是当区间长度是偶数的时候 我们取他的左边那位 

    }
    cout<<ans<<endl;
}