1 条题解

  • 0
    @ 2025-10-8 16:54:01
    #include <bits/stdc++.h>
    using namespace std;
    int a[110000], s[110000];
    map<int, int> ss;
    int main()
    {
        int n, b, p, ans=1; scanf("%d%d", &n, &b);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            if(a[i]==b) a[i]=0, p=i;   //等于 b为 0,p记录位置 
            else  a[i]=(a[i]>b)? 1: -1;  //比 b大的为 1,比 b小的为 -1 
        }
        
        for(int i=p+1; i<=n; i++)
            s[i] += s[i-1] + a[i], ss[s[i]]++;  // 求右边的前缀和序列
        for(int i=p-1; i>=1; i--)
        {
            s[i] += s[i+1] + a[i];  // 左边的后缀和序列
            int x = s[i] * -1;
            if(ss.count(x)) ans += ss[x];  //查找是否有相反数 
            if(s[i] == 0) ans++;   //0也是相反数 
        }
        
        if(ss.count(0)) ans += ss[0];   //右边 0的个数 
        printf("%d\n", ans);
        return 0;
    }
    
    • 1

    *【中位数(难度:8)】中位数

    信息

    ID
    781
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    17
    已通过
    12
    上传者