3 分钟 读完 (大约 375 个字)
牛客网NOIP赛前集训营-提高组（第一场）中位数
题解
- 对于第一档数据,可以枚举选取的合法的子区间,再重新排序, 直接得到中位数。时间复杂度$O(n^3)$。
- 对于第二档数据,可以枚举子区间的左端点,依次往右增加新的数,现在要做的就是往一个有序列表里加数,然后查询第k小的值。这个可以用平衡树维护。总复杂度就是$O(n^2logn)$。
- 对于第三档数据,直接枚举最终可能的答案x。把数字大于等于$x$的记为1,小于$x$的记为-1。检验是否存在和$>=0$的区间。可以维护一个前缀和的前缀最大值。时间复杂度$O(Mn)$, M为不同的数的个数。
- 正解:发现第三档数据中的$x$其实是可以二分的。那么二分答案$x$,用上面的方法检验。时间复杂度$O(nloga_i)$。
代码
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
| #include<bits/stdc++.h>
#define RG register
using namespace std;
multiset<int> s;
const int maxn(1e5 + 10);
int n, a[maxn], len, ans, b[maxn];
inline bool check(int mid)
{
for(RG int i=1;i<=n;i++) b[i] = a[i] < mid ? -1 : 1;
int _min = INT_MAX;
for(RG int i=1;i<=n;i++)
{
b[i] += b[i-1];
if(i >= len) { _min = min(_min, b[i-len]); if(b[i] - _min > 0) return true; }
}
return false;
}
int main()
{
scanf("%d%d", &n, &len);
for(RG int i=1;i<=n;i++) scanf("%d", &a[i]);
long long l = 1, r = 1e9 + 1, ans = -1;
while(l <= r)
{
int mid((l + r) >> 1);
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
printf("%lld\n", ans);
return 0;
}
|