当前位置：网站首页>【集训DAY3】中位数

【集训DAY3】中位数

2022-08-09 22:35:00 【VL——MOESR】

在这里插入图片描述

思路：

从中间往左扫
我们用一个桶存它比他大的个数出现的次数
然后在往右扫统计答案

$co d e$

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 1e5 + 10;

int n, b;
int a[MAXN], g[2][MAXN * 2];
int ans;

int main() {
    
	scanf("%d%d", &n, &b);
	int p = 0;
	for(int i = 1; i <= n; i ++) {
    
		scanf("%d", &a[i]);
		if(a[i] == b) p = i;
	}
	int tmp = 0;
	for(int i = p; i >= 1; i --) {
    
		if(a[i] < a[p]) tmp ++;
		else tmp --;
		g[(p - i) % 2][tmp + MAXN] ++;
	}
	tmp = 0;
	for(int i = p; i <= n; i ++) {
    
		if(a[i] > a[p]) tmp ++;
		else tmp --;
		ans += g[(i - p) % 2][tmp + MAXN];
	}
	printf("%d", ans);
	return 0;
}