题解 P1627 【中位数】

##### [题目传送门](https://www.luogu.org/problem/show?pid=1627) ## 思路 ### 标记一遍相对大小，大的标1，小的标-1。只要连续 n 项和为0，就能满足题目条件。 ### 首先一遍找到中位数位置 pos，放个数组 flag 标记查找中的数与目标中位数的相对大小： 1 -> 比中位数大 -1 -> 比中位数小 0 -> 找到中位数！标记pos 还是举个实例吧…… 数组：1 1 -1 -1 -1 pos 1 -1 1 ### 然后从 (pos - 1) 走一遍到1，也就是反过来。再拿一个变量 sum 标记每往左走一个时数组 flag 这一项与这之前的项之和。怎么标？用哈希的方法！（开个数组 f ）那万一 sum 值为负怎么办？数组的下标可没有负的！凉拌~ 把所有 sum 值统统加上一个足够大的值 "KEY" 。妈妈再也不用担心下标的值为负啦！ 这时的 sum 数组：-1 -2 -3 -2 -1 这时的 f 数组：f [ -1 + KEY ] = 2 ; f [ -2 + KEY ] = 2 ; f [ -3 + KEY ] = 1 ; ### 做完这些以后，最后从 (pos + 1) 走一遍到 n ,正着走。和上边一样，记录 sum 值。不过这次得多一个步骤——每次要找 pos 左边的对应值。 从 pos 向右 1. sum=1 -> 左边 sum=-1 -> 两次 ∴ ans+=2; 2. sum=0 -> 左边 sum=0 -> 无 3. sum=1 -> 左边 sum=-1 -> 两次 ∴ ans+=2; ### 最后输出 ans 即可。 C++ 代码如下： ```cpp #include <cstdio>//头文件 #include <cstdlib>//头文件 using namespace std;//命名空间 #define KEY 100001//定义一个足够大的数 int n,b,pos,a[100010],flag[100010],f[200010],s,ans; int main(){ scanf("%d%d",&n,&b);//输入 for(int i=1;i<=n;i++){//第一次循环 scanf("%d",&a[i]); if(a[i]==b) pos=i;//就是中位数 else if(a[i]>b) flag[i]=1;//大的标1 else flag[i]=-1;//小的标-1 } for(int i=pos-1;i>=1;i--){//第二次循环 s+=flag[i];//计算此次sum值 f[s+KEY]++; if(s==0) ans++;//找到满足题意只在 pos 左侧的连续子序列！ } s=0;//为第三次循环的累加做准备 for(int i=pos+1;i<=n;i++){//第三次循环 s+=flag[i];//计算此次sum值 if(s==0) ans++;//找到满足题意只在 pos 右侧的连续子序列！ ans+=f[-s+KEY]; } printf("%d\n",++ans);//还少一次只由 pos 自己组成的连续子序列（也满足条件！） return 0; } ```