BZOJ 1303 CQOI2009 中位数图 水题

1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 2340  Solved: 1464[Submit][Status][Discuss]

Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

Input

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4 5 7 2 4 3 1 6

Sample Output

4

HINT

第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}N<=100000

Source

  [ Submit][ Status][ Discuss]

--------------------------------------------------------

水题。

记录x的位置m

记录从m+1开始的序列[m+1,i]中每一个比X大的数bg减去比x小的数sm 并统计每一个bg-sm的个数

在从m-1开始到1 统计 bg-sm  在之前的表中寻找 sm-bg的个数这个个数就是m为中位数的序列个数

一开始 num(0)=1 因为一开始m一个数也可以

代码如下:

#include<cstdio> #include<iostream> #include<cstring> #define For(i,x,y) for(int i=x;i<=y;++i) #define Forn(i,x,y) for(int i=x;i>=y;--i) using namespace std; #define N 300000 int num[N],a[N]; #define num(x) num[x+100000] int main() { int n,x,m;cin>>n>>x; For(i,1,n){scanf("%d",&a[i]);if(a[i]==x)m=i;} int bg=0,sm=0; num(0)=1; For(i,m+1,n) { if(a[i]>x)bg++; if(a[i]<x)sm++; num(bg-sm)++; } int ans=num(0);bg=0;sm=0; Forn(i,m-1,1) { if(a[i]>x)bg++; if(a[i]<x)sm++; ans+=num(sm-bg); } cout<<ans; }

 

转载于:https://www.cnblogs.com/rwy233/p/6008005.html