M_sea

洛谷1627 中位数
题目描述给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排...
扫描右侧二维码阅读全文
01
2017/10

洛谷1627 中位数

题目描述

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

传送门

算法

这道题需要数学知识。

首先,对于一个有奇数个元素的区间(i,j),仅当比k小的数等于比k大的数时k是中位数。
所以记录中位数的下标indexk,然后往左统计区间(i,indexk)内比k大的数。往右同理。

在往左找时,如果出现比k大的数为0,就ans++。
在往右找时,对于每个区间(indexk+1,i)内比k大的数(设为s),则要使k时区间(j,i)的中位数,必须满足(i,indexk)内比k大的数+(indexk+1,j)内比k大的数=0。
注意这里比k大的数可以是负数,如当a[indexk-1]比k小时(indexk-1,indexk)内比k大的数为-1。

所以统计(indexk+1,n)内所有的t[s]的和即可,其中t[i]表示比k大的数为i的区间数。

注意到i会有负数,要统一加上一个值。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int a[100010]; //输入的排列
int t[800010]; //t[i]的意义如上
int main()
{
    int n,k,indexk=1; scanf("%d%d",&n,&k); //输入
    for (re int i=1;i<=n;i++) {
        scanf("%d",&a[i]); //输入
        if (a[i]==k) indexk=i; //找到中位数的下标
    }
    int ans=0,s=0;
    for (re int i=indexk;i>=1;i--) { //往左找
        if (a[i]>k) s++; //大于就++
        if (a[i]<k) s--; //小于就--
        if (s==0) ans++; //等于0答案就++
        t[s+100001]++; //累加区间
    }
    s=0;
    for (re int i=indexk+1;i<=n;i++) {
        if (a[i]>k) s++; //同上
        if (a[i]<k) s--;
        ans+=t[-s+100001]; //答案累加相反的区间
    }
    printf("%d\n",ans); //输出
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 17 PM

发表评论