中位数

给出1～n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。

中位数的定义可以转化为在序列中大于它和小于它的数的个数相等。

序列总数就是以它为左端点的+以它为右端点的+它不做端点的

怎么求看代码

View Code

 1 program median(input,output);
 2 var
 3    f,a          : array[-100000..110000] of longint;
 4    n,i,x      : longint;
 5    max,pos,answer : longint;
 6 begin
 7    assign(input,'median.in');reset(input);
 8    assign(output,'median.out');rewrite(output);
 9    readln(n,x);
10    fillchar(f,sizeof(f),0);
11    for i:=1 to n do
12    begin
13       read(a[i]);
14       if a[i]=x then
15      pos:=i;
16    end;
17    max:=0;
18    answer:=0;
19    for i:=pos+1 to n do
20    begin
21       if a[i]>x then
22      inc(max)
23       else
24      dec(max);
25       if max=0 then
26      inc(answer);//左端点
27       inc(f[max]);
28    end;
29    max:=0;
30    for i:=pos-1 downto 1 do
31    begin
32       if a[i]>x then
33      inc(max)
34       else
35      dec(max);
36       if max=0 then
37      inc(answer);//右端点
38       inc(answer,f[-max]);//不做端点的
39    end;
40    writeln(answer+1);//自己也是一个序列
41    close(input);
42    close(output);
43 end.