中位數計數

5
1 2 3 4 5

1 2 3 2 1

問題鏈接：HDU5701 中位數計數。

統計學中位數計算例題？問題簡述：參見上文。

問題分析：統計比它大的（正）和比它小的（負）數的個數，再進行計算。

程序說明：（略）

AC的C++語言程序如下：

中位數例題和答案。

/* HDU5701 中位數計數 */#include <iostream>
#include <cstring>using namespace std;const int MAXN = 8000;int v[MAXN+1], count[2*(MAXN+1)];int main()
{int n, ans, cnt;while(cin >> n) {for(int i=1; i<=n; i++)cin >> v[i];for(int i=1; i<=n; i++) {memset(count, 0, sizeof(count));cnt = 0;count[n]++;for(int j=1; j<i; j++) {if(v[i - j] < v[i])cnt--;elsecnt++;count[n + cnt]++;}cnt = 0;ans = count[n];for(int j=1; i+j<=n; j++) {if(v[i+j] < v[i])cnt--;elsecnt++;ans += count[n - cnt];}if(i==n)cout << ans << endl;elsecout << ans << " ";}}return 0;
}