BestCoder Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 271 Accepted Submission(s): 112
Problem Description
Mr Potato is a coder.
Mr Potato is the BestCoder.
One night, an amazing sequence appeared in his dream. Length of this sequence is odd, the median number is M, and he named this sequence as Bestcoder Sequence.
As the best coder, Mr potato has strong curiosity, he wonder the number of consecutive sub-sequences which are bestcoder sequences in a given permutation of 1 ~ N.
Mr Potato is the BestCoder.
One night, an amazing sequence appeared in his dream. Length of this sequence is odd, the median number is M, and he named this sequence as Bestcoder Sequence.
As the best coder, Mr potato has strong curiosity, he wonder the number of consecutive sub-sequences which are bestcoder sequences in a given permutation of 1 ~ N.
Input
Input contains multiple test cases.
For each test case, there is a pair of integers N and M in the first line, and an permutation of 1 ~ N in the second line.
[Technical Specification]
1. 1 <= N <= 40000
2. 1 <= M <= N
For each test case, there is a pair of integers N and M in the first line, and an permutation of 1 ~ N in the second line.
[Technical Specification]
1. 1 <= N <= 40000
2. 1 <= M <= N
Output
For each case, you should output the number of consecutive sub-sequences which are the Bestcoder Sequences.
Sample Input
1 1
1
5 3
4 5 3 2 1
Sample Output
1
3HintFor 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;
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。