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

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

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

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

#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;
}

最后

以上就是明理小伙为你收集整理的Codeforces Round #496 E1. Median on Segments (Permutations Edition)(思路)的全部内容，希望文章能够帮你解决Codeforces Round #496 E1. Median on Segments (Permutations Edition)(思路)所遇到的程序开发问题。

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