51Nod题目链接：点击打开题目

HDU题目链接：点击打开题目

中位数计数

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1285    Accepted Submission(s): 481 Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个数值的平均数作为中位数。 现在有 n 个数，每个数都是独一无二的，求出每个数在多少个包含其的区间中是中位数。   Input 多组测试数据 第一行一个数 n(n≤8000) 第二行 n 个数， 0≤ 每个数 ≤109 ,   Output N 个数，依次表示第 i 个数在多少包含其的区间中是中位数。   Sample Input 5 1 2 3 4 5   Sample Output 1 2 3 2 1   Source 2016"百度之星" - 初赛（Astar Round2B）    

中文题：

1682 中位数计数 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题  收藏  关注

中位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个数值的平均数作为中位数。

现在有n个数，每个数都是独一无二的，求出每个数在多少个包含其的区间中是中位数。

Input 第一行一个数n(n<=8000) 第二行n个数，0<=每个数<=10^9 Output N个数，依次表示第i个数在多少包含其的区间中是中位数。 Input示例 5 1 2 3 4 5 Output示例 1 2 3 2 1

还是思维的问题。

分别计算该数之前之后比它大的、比它小的数。遇到一个大的就+1，一个小的就-1，遇到0就直接在ans上计数。

然后扫到右边的时候，如果碰到和前面的数互为相反数的时候，那么以这个数为右区间，可以和前面的每一个该数量的数都形成一个区间。复杂度：O（n^2）

代码如下：

#include <stdio.h> #include <cstring> #include <algorithm> using namespace std; #define CLR(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define LL long long const int mid = 8000; int main() { int n; int num[8011]; int cnt[8005<<1]; int ant,ans; while (~scanf ("%d",&n)) { for (int i = 1 ; i <= n ; i++) scanf ("%d",&num[i]); for (int i = 1 ; i <= n ; i++) { CLR(cnt,0); ant = 0; cnt[mid]++; //自己单独的区间 for (int j = i - 1 ; j >= 1 ; j--) { if (num[j] > num[i]) ant++; else ant--; cnt[mid+ant]++; } ans = cnt[mid]; //每一个0都是一个小区间 ant = 0; for (int j = i + 1 ; j <= n ; j++) { if (num[j] > num[i]) ant++; else ant--; ans += cnt[mid-ant]; //每和前面的互为相反数就多一个该数的个数 } printf ("%d",ans); if (i == n) puts(""); else printf (" "); } } return 0; }