【每日一题】中位数图

[CQOI2009]中位数图

http://www.nowcoder.com/questionTerminal/e80eb142b3c044efb70113114cb27cea

思路:








#include <cstdio>
#include <map>
using namespace std;
const int N = 1e5+10;
map<int,int> mp;
int a[N];
int main(){
    int n,b,pos;scanf("%d%d",&n,&b);
    for(int i = 1;i <= n;i++){
        scanf("%d",a+i);
        if(a[i] == b) pos = i; 
    }
    int tmp = 0;
    for(int i = pos;i <= n;i++){
        if(a[i] > b) tmp++;
        if(a[i] < b) tmp--;
        mp[tmp]++;
    }
    tmp = 0;
    int ans = 0;
    for(int i = pos;i >= 1;i--){
        if(a[i] > b) tmp++;
        if(a[i] < b) tmp--;
        ans += mp[0-tmp]; 
    }
    printf("%d\n",ans);
    return 0;
}
全部评论

相关推荐

10-09 17:17
已编辑
门头沟学院 Java
活泼的代码渣渣在泡池...:同学你好,我也是学院本,后天要面这个亚信科技,是实习,请问问题都啥样呀,我项目就做了网上的,这是第一次面试
投递多益网络等公司10个岗位
点赞 评论 收藏
分享
野猪不是猪🐗:😇:恭喜你以出色的表现成为xxx的一员 😨:您以进入本公司人才库 实际点开:您愿望单中的xxx正在特卖!
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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