【每日一题】中位数图

[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;
}
全部评论

相关推荐

熊大不大:微信也是华为旗下吧,我看我朋友也是华为工牌写wx
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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