题解 P1627 【中位数】

distantlight · 2017-08-16 11:53:41 · 题解

思路楼下都说了，简单总结下

1.只关心相对大小，所以数字可以转为1，-1，0。要求覆盖b位置的总和为0的连续子序列数量

2.用部分和，只要求左右部分和相等的对数

3.由于部分和的范围是有界的，使用计数排序即可，复杂度O(n)

下面是比较短的代码实现

#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;
}