问题链接: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--;
else
cnt++;
count[n + cnt]++;
}
cnt = 0;
ans = count[n];
for(int j=1; i+j<=n; j++) {
if(v[i+j] < v[i])
cnt--;
else
cnt++;
ans += count[n - cnt];
}
if(i==n)
cout << ans << endl;
else
cout << ans << " ";
}
}
return 0;
}