牛客——中位数图(思维)

[CQOI2009]中位数图 (思维)

思路:

感觉这个题很偏向思维,原谅本蒟蒻看了题解后才想明白。

首先要考虑到的就是题目中的大小关系都只是一个相对的关系,所以大于b的数对答案的贡献都是一样的,小于b的数对答案的贡献都是一样的。不妨就设大于b的数的值为1,小于b的数的值为-1,等于b的数的值为0。

所以问题就转化成了求一个区间和为0的而且内部元素有0的长度为奇数的区间个数。

因为1和-1要相互抵消,而区间内又必须含有0,所以区间的长度就一定是奇数。

所以可以以0为起点,分别统计前后缀,前缀和为x时,后缀和一定为-x才能符合题意。所以分别用l,r两个数组表示和为x的数的个数,最后遍历一遍求出结果即可。

因为数组的下标不可以为负数,所以要同时平移,当所有的数都是-1时,和为-n,所以平移n个单位即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=110000;

int a[maxn],l[maxn],r[maxn],sum[maxn];

int main(){
    int n,b;
    cin>>n>>b;
    int pos;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>b) a[i]=1;
        else if(a[i]<b) a[i]=-1;
        else a[i]=0,pos=i;
    }
    l[n]=r[n]=1;
    for(int i=pos+1;i<=n;i++) sum[i]=sum[i-1]+a[i],r[sum[i]+n]++;
    for(int i=pos-1;i>=1;i--) sum[i]=sum[i+1]+a[i],l[sum[i]+n]++;
    int res=0;
    for(int i=0;i<2*n;i++) res+=(l[i]*r[2*n-i]);
    cout<<res<<endl;

    return 0;
}
全部评论
大佬好强啊
点赞 回复 分享
发布于 2020-05-24 20:44

相关推荐

07-24 19:01
门头沟学院 Java
后天笔试,又要开始做题了
Sairus:明天10:00笔试
投递京东等公司10个岗位
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务