此题做法同这个题,之前做过,但是真的是惭愧,自己写在博客上的东西真的很少拿出来看了.掌握的也不扎实,理解不透，一般也就记个几天时间.唉。。。
题目链接
还是和以前的做法一样,先记录这个数的左面比他大的数的个数与比它小的数的个数的差,然后再看这个数右面的,比它小的数的个数与比它大的个数的差,记录对应的值,另外不要忘了该数本身（可以看成差为0的),和左面右面各自为0的情况.
#include<bits/stdc++.h> using namespace std; const int maxn=1e4+10; int n,m; int ans[8*maxn]; int s[8*maxn]; int vis[8*maxn]; int main() { while(~scanf("%d %d",&n,&m)) { memset(ans,0,sizeof(ans)); memset(vis,0,sizeof(vis)); int mid; for(int i=1;i<=n;i++) { scanf("%d",&s[i]); if(s[i]>m) vis[i]=1; else if(s[i]<m) vis[i]=-1; else { vis[i]=0; mid=i; } } int s=0; int cnt=0; ans[4*maxn]++;//自己本身的情况 for(int i=mid-1;i>0;i--) { cnt+=vis[i]; ans[cnt+4*maxn]++; } s+=ans[4*maxn];//左面就构成中位数的情况 cnt=0; for(int i=mid+1;i<=n;i++) { cnt-=vis[i]; s+=ans[cnt+4*maxn]; } printf("%d\n",s); } } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
