BestCoder Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 271    Accepted Submission(s): 112

1 1

1

5 3

4 5 3 2 1

1

3

Hint

For the second case, {3},{5,3,2},{4,5,3,2,1} are Bestcoder Sequence.

题目意思是  再给出的全排列(1~n每一个数字仅仅出现一次)中,找到一个奇数个的子串,要求子串的中位数(大小排序后正中间的数), 为M;

求这样的子串有多少.

首先要把M这个数左边的串预处理下,  假设 遇到大于M的数ji++,然后记录在data[当前位置的奇偶][当前记录的ji]  ,假设当前位置的数小于M的数,ji--; 由于ji记录在数组里,所以ji 要价格50000 以保证不会出现负数的情况.

然后再处理右边的串,ji 又一次计数,

ans+data[位置奇偶, 假设两个位置奇偶同样,代表这条串有奇数个元素][-ji  加个符号,找到前面处理过的左串中,能够互补的串,达到大于M的数和小于M的数 一样多];

相同加个ji取负数后  相同加个 50000,和前面保存一致

#include<stdio.h>

#include<string.h>

int big(int a)

{

	return a+50000;

}

int a[50000],ji,data[2][200000];

int main()

{

	int n,m,i,j,wei;

	int ans;

	while(scanf("%d%d",&n,&m)!=EOF)

	{

		ans=0;

		for(i=1;i<=n;i++)

		{

			scanf("%d",&a[i]);

			if(a[i]==m)

				wei=i;

		}

		ji=0;

		memset(data,0,sizeof(data));

		for(i=wei;i>=1;i--)

		{

			if(a[i]<m)

				ji--;

			if(a[i]>m)

				ji++;

			if(i&1)

				data[1][big(ji)]++;

			else

				data[0][big(ji)]++;

		}

		ji=0;

		for(i=wei;i<=n;i++)

		{

			if(a[i]<m)

				ji--;

			if(a[i]>m)

				ji++;

			if(i&1)

				ans+=data[1][big(-ji)];

			else

				ans+=data[0][big(-ji)];

		}

	    printf("%d\n",ans);

	}

	return 0;

}