题解 P1627 【中位数】

distantlight

2017-08-16 11:53:41

Solution

思路楼下都说了,简单总结下 1.只关心相对大小,所以数字可以转为1,-1,0。要求覆盖b位置的总和为0的连续子序列数量 2.用部分和,只要求左右部分和相等的对数 3.由于部分和的范围是有界的,使用计数排序即可,复杂度O(n) 下面是比较短的代码实现 ```cpp #include <iostream> #define N 100005 using namespace std; long long n,b,ans,c[2][2*N]; int main () { cin>>n>>b; c[0][n]=1; for (long long i=0,a,s=n,isRight=0;i<n;i++){ cin>>a; if (a!=b) s+=a>b?1:-1; c[isRight|=a==b][s]++; } for (long long i=0;i<2*n;i++,ans+=c[0][i]*c[1][i]); cout<<ans<<endl; return 0; } ```