KMedian Subsequence

【原题链接】

【题意说明】

1~N这N个不同的数构成的序列,从其中选择一段连续奇数个数,使得这些数中的中位数为指定的K!问共有多少种方案?

【问题分析】

首先本题的指示中特别指出:The Median is the "middle number"  in a sorted list of numbers.其意思就是说:中位数是排序后的中间的那个数!

当然本题不能把每种选择方案的数进行排序,然后比较其中间数是否为指定的K,由于所选的序列一定要包括K,所以可以先找出K然后由K向两边生成序列即可!

再由于所选数的个数为奇数个,所以只需要记录比K大的个数a[i]和比K小的个数b[i],若a[i]==b[i]则就是一种方案!

例外,在向两扩展时,可以考虑先向一边扩展,边扩展记录比k当前位置的大于K与小于K的数个数之差c[a[i]-b[i]]++ {负数时可以加个基数处理一下}!再向另一个方向扩展时,除了本身的a[i]==b[i]时之外还要考虑c[b[i]-a[i]]的个数,这也是它的方案数!

原文地址:https://www.cnblogs.com/ahmasoi/p/2784736.html