首页 > 代码库 > CQOI2009 BZOJ1303 中位数

CQOI2009 BZOJ1303 中位数

2024-11-04 07:35:01   204人阅读

 

首先找出b在数列中的位置mid

用 f[i]记录mid左边从mid往左统计比m小的数与比m大的数的差值为i的个数

用g[i]记录mid右边从mid往右统计比m大的数与比m小的数的差值为i的个数

。。有点语死早，找个样例模拟一下就懂了

 1 var n,b,mid,k,I:longint; 2     ans:int64; 3     a:array[0..100008] of longint; 4     f,g:array[-100008..100008] of longint; 5 begin 6     readln(n,b); 7     for i:=1 to n do 8     begin 9         read(a[i]);10         if b=a[i] then mid:=i;11     end;12     k:=1;13     for i:=mid downto 1 do14     begin15         if a[i]>a[mid] then dec(k);16         if a[i]<a[mid] then inc(k);17         inc(f[k]);18     end;19     k:=1;20     for i:=mid to n do21     begin22         if a[i]>a[mid] then inc(k);23         if a[i]<a[mid] then dec(k);24         inc(g[k]);25     end;26     for i:=-n to n do ans:=ans+f[i]*g[i];27     writeln(ans);28 end.

 

CQOI2009 BZOJ1303 中位数


联系
我们