【每日一题】中位数图
[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;
}