HBC24120等差数列[USACO 2011 Nov G]Above the Median题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

Farmer John has lined up his N (1

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height Hi(1<=Hi<=1,000,000,000)H_i (1 <= H_i <= 1,000,000,000)Hi​(1<=Hi​<=1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair. The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000). For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of 7,3,2,6{7, 3, 2, 6}7,3,2,6 is 6, and the median of 5,4,8{5, 4, 8}5,4,8 is 5. Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest. 给出一串数字，问中位数大于等于X的连续子串有几个。（这里如果有偶数个数，定义为偏大的那一个而非中间取平均）

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24120等差数列[USACO 2011 Nov G]Above the Median题解