Fork me on GitHub

[51NodP1682] 中位数计数

传送门

发现题目中的数据范围说明我们需要一个时间复杂度为$O(n^2)$的算法.
发现我们可以考虑每个数字的贡献,我们发现,对于某个位置上的数字而言,包含这个位置的区间的数量是$n$级别的.
所以我们可以尝试对于每个位置的数字,枚举包含这个位置的区间然后统计答案.
所以问题就转化成了怎么统计答案.由于权值的范围很大,所以我们考虑设$sum_{n+j}$表示排序后,与$i$这个位置的数字还需要移动正负$j$个单位才能到中位数的位置.
然后我们枚举完所有区间之后直接统计就好了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
const int N = 8e3 + 5;
const int INF = 0x3f3f3f3f;
int n;
int num[N], sum[N << 1], ans[N];
int main ( void ) {
ios :: sync_with_stdio ( false );
cin.tie ( 0 ) , cout.tie ( 0 );
cin >> n;
for (int i = 0; i < n; i++)
cin >> num[i];
for (int i = 0; i < n; i++){
memset(sum, 0, sizeof(sum));
int cnt = 0;
for (int j = i; j >= 0; j--){
if (num[j] > num[i])
cnt++;
if (num[j] < num[i])
cnt--;
sum[8000+cnt]++;
}
cnt = 0;
for (int j = i; j < n; j++){
if (num[j] > num[i])
cnt++;
if (num[j] < num[i])
cnt--;
ans[i] += sum[8000-cnt];
}
}
for (int i = 0; i < n; i++){
cout << ans[i];
if (i != n-1)
cout << " ";
else
cout << endl;
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[51NodP1682] 中位数计数

文章作者:KRrrrrrrrr

发布时间:2019年10月24日 - 20:10

最后更新:2019年10月24日 - 20:10

原始链接:http://krrrr.xyz/2019/10/24/51Nod-P1682中位数计数/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。