每日一题 [CQOI2009]中位数图

题目描述

给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元>素从小到大排列后，位于中间的数。

输入描述:

第一行为两个正整数n和b ，第二行为1~n 的排列。
对于 30% 的数据中，满足 n≤100；
对于 60% 的数据中，满足 n≤1000；
对于 1100% 的数据中，满足n≤100000,1≤b≤n。
输出描述:
输出一个整数，即中位数为b的连续子序列个数。
直接暴力o(n^3) 铁定tle
可以想见应该是思维转化的题目 中位数在排序过后比他大的个数和比他小的个数相同
具体数值对题目没有影响 所以将小于k的数值改为-1 大于k的数值改为1
左右两端个数的比较也就显而易见 看区间和是否为0

不妨先来看看连续子序列和为k
前缀和+暴力枚举 显然不够
sum代表从初始位置到当前位置之和
hash_cmp[sum]代表sum出现的次数
那么就只要找到一个sum-k的值的出现次数就行

for (int i=0;i<n;++i)
{
   sum+=a[i];
   cnt+=hash_cmp[sum-k];
   ++hash_cmp[sum]
}

但是这题需要将中位数放进去
所以我们只要找到他的位置
从左边枚举连续位置
再从右边直接找就行 此时不必记录，因为此时记录的是右边的出现次数

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn];
map<int,int>hash_map;///负数也方便处理
int main()
{
  int n,k;
  cin>>n>>k;
  int w=0;
  for (int i=0;i<n;++i)
  {
    cin>>a[i];
    if (a[i]<k)a[i]=-1;
    if (a[i]>k)a[i]=1;
    if (a[i]==k)
    {
       a[i]=0;
       w=i;///记录位置
    }
  }
  int ans=0;
  for (int i=w;i>=0;--i)///为了连续，一定要从w-0的方向枚举
  {
    ans+=a[i];
    hash_map[ans]++;
  }
  int sum=0;
  long long cnt=0;///别忘了开longlong
  for (int i=w;i<n;++i)
  {
     sum+=a[i];
     cnt+=hash_map[0-sum];///找到左边区段的记录就行
  }
  cout<<cnt<<endl;
  return 0;
}