一、题目内容

题目描述

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

输入描述：

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

输出描述：

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

示例1

输入

7 4
5 7 2 4 3 1 6

输出

4

二、解题思路

乍一看，有没有给数组一个快速排序的冲动？小的放左边，大的放右边，balabalabala。其实这里并没有快排这么多工序，我们知道初始化比较值b，在读入数组(a)过程中，同时初始化一个相同size的数组(flag)，将当前下标的值与b的大小关系并存储在相应的位置，小于b的为-1，大于b的为1。接下来，以b为中点：

1.我们需要先遍历左边的，使用s保留每次叠加的值（s = $\sum^{n}_{i->n}{flag_i}$ ），使用数组f记录当前值s为下标的个数【用于右侧遍历时使用】，若s = 0，则符合题意要求，所以ans+1；
2.然后再遍历右边的，同样若s = 0，则ans+1，若当前值s取反为下标在数组f中有意义，则ans += f[-s + MAXN]【这是因为左边树我们已经在数组f保存过节点s（下标）具有的值，若右边树节点s（下标）在f处有值，则构成中位数图，那么新增f在s处的值的组合数】；
3.最终我们再算上"b"自己，则++ans为最终结果。

代码实操

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int a[MAXN], f[MAXN * 2], flag[MAXN], pos;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, b;
    cin >> n >> b;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == b) {
            pos = i;
        } else if (a[i] < b) {
            flag[i] = -1;
        } else {
            flag[i] = 1;
        }
    }
    int s = 0, ans = 0;
    ///左边
    for(int i = pos - 1; i >= 1; i--) {
        s += flag[i];
        f[s + MAXN]++;
        if (s == 0) ans++;
    }
    s = 0;
    ///右边
    for(int i = pos + 1; i <= n; i++) {
        s += flag[i];
        if (s == 0) ans++;
        ans += f[-s + MAXN];
    }
    cout << ++ans << endl;
    return 0;
}

最后编辑于：2019.12.09 16:24:49