Loading...

洛谷P1627 [CQOI2009]中位数

check评论:0 条 remove_red_eye浏览量:361 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-16

前缀和的思想owo

这道题只关心与$b$的相对大小,所以将小于$b$的数设为$-1$,大于的设为$1$就好

然后只要某个包含$b$的区间和为$0$即可,$map$记录后扫一遍统计答案就好

用的$map$所以复杂度$O(nlogn)$owo

#include <bits/stdc++.h>
using namespace std;
int sum[1000010];
map<int,int> mp[2];
int main()
{
    int n,b,pos=0;
    cin>>n>>b;
    mp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x>b)
        {
            x=1;
        }
        else if(x==b) 
        {
            pos=i;
            x=0;
        }
        else
        {
            x=-1;
        }
        sum[i]=sum[i-1]+x;
        if(pos==0)
        {
            mp[i&1][sum[i]]++;
        }
    }
    int ans=0;
    for(int i=pos;i<=n;i++)
    {
        ans+=mp[!(i&1)][sum[i]];
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名