入门OJ 4246： [Noip模拟题]中位数

发表于 更新于 分类于

题目

Description

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

Input

第一行为两个正整数n(n<=100000)和b(1<=b<=n)，第二行为1~n 的排列。 ## Output 输出一个整数，即中位数为b的连续子序列个数。 ## Sample Input 

1
2
7 4
5 7 2 4 3 1 6
## Sample Output 
1
4
样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}。 # 题解

类似于计数排序的方法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int n, b, ans, left_right[2][200010];
int main(int argc, char **argv) {
    scanf("%d %d", &n, &b); 
    left_right[0][n] = 1;
    for (register int i(0), a, s(n), right(0); i < n; ++i) {
        scanf("%d", &a);
        if (a != b) s += a > b ? 1 : -1;
        ++left_right[right |= a == b][s];
    }
    for (register int i(0); i < n << 1; ans += left_right[0][++i] * left_right[1][i]);
    cout << ans << endl;
    return 0;
}