M_sea

洛谷1627 中位数
Luogu算法这道题需要数学知识。首先,对于一个有奇数个元素的区间$[i,j]$,仅当比$k$小的数等于比$k$大...
扫描右侧二维码阅读全文
01
2017/10

洛谷1627 中位数

Luogu

算法

这道题需要数学知识。

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

在往左找时,如果出现比$k$大的数为0,就ans++。
在往右找时,对于每个区间$[indexk+1,i]$内比$k$大的数(设为$s$),则要使$k$时区间$[j,i]$的中位数,必须满足$[i,indexk]\text{内比}k\text{大的数}+[indexk+1,j]\text{内比}k\text{大的数}=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;
}
最后修改:2019 年 05 月 26 日 02 : 14 PM

发表评论