题目描述
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
输入描述:
第一行为两个正整数n和b ，第二行为1~n 的排列。
输出描述:
输出一个整数，即中位数为b的连续子序列个数。
题解
对于这道题，我们想求的是一个大于k和小于k的数字的数量相等且包含k的区间，我们可以把大于k的数字统一看成1，小于k的数字看作-1，k看作0，来求一个前缀和序列。
比如我们用样例来举一个例子：
7 4 原数列： 5 7 2 4 3 1 6 对应的前缀和数列：0 1 2 1 1 0 -1 0我们要求的序列必定满足一下条件：
1. 若序列为l到r，那么l-1与r的前缀和必定相等。因为他们之间经过了相同数量的大于k和小于k的数字，此段和应为0。
2. 必须保证l-1和r不在k的同一侧。
所以我们就可以愉快的写一个前缀和代码啦~
我把需要注意的地方在代码里写上了注释，大家在写的时候一定要注意细节哟
完整代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5;
int a[100500];
int sum[200500];//用来记录有多少位置的值为m，开两倍是为了防止负数下标，把所有前缀和+N,也可以直接开一个map
int n,k;
int main(){
scanf("%d%d",&n,&k);
bool flag=false;//判断是否过了k这个数字
int ans=0;//答案
sum[N]=1;//N相当于0+N，及前缀和为0的，最开头的地方即什么数也没有的时候前缀和是0
for(int i=1;i<=n;++i){
int num;
scanf("%d",&num);
if(num==k){
flag=true;
a[i]=a[i-1];
}
else a[i]=a[i-1]+(num>k?1:-1);//计算前缀和
if(flag)ans+=sum[a[i]+N];//如果已经过了k了，那么我们就可以计算了
if(!flag)sum[a[i]+N]++;//之有没有过k的地方才可以做l，如果没有这句话你就要判断奇偶了
//对于样例来理解这句代码
//样例3这个数字的前缀和为0，6也为0，但从3到6并不是合法区间，因为他们并不位于k两侧
}
printf("%d",ans);
} 
京公网安备 11010502036488号