题目信息
题目来源:CCF 重庆省选 2009;
在线评测地址:Luogu#1627;
运行限制:时间不超过 (1.00 extrm{s}),空间不超过 (128 extrm{MiB})。
题目描述
给出 (1,2,cdots,n) 的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是 (b)。中位数是指把所有元素从小到大排列后,位于中间的数。
输入格式
第一行为两个正整数 (n) 和 (b),第二行为 (1,2,cdots,n) 的排列。
输出格式
输出一个整数,即中位数为 (b) 的连续子序列个数。
数据规模与约定
- 对于 (30\%) 的数据中,满足 (nle 100);
- 对于 (60\%) 的数据中,满足 (nle 1000);
- 对于 (100\%) 的数据中,满足 (nle 10^5),(1le ble n)。
分析
插一句题外话,这道题与 CSP-S2019 D1T2 有异曲同工之妙。
(30 exttt{pts})
枚举所有连续子序列,暴力排序找中位数。
复杂度:(mathcal{O}(n^3log n))
(60 exttt{pts})
我们观察一下这种子序列的条件:
- 连续且包含 (b) 这个元素;
- (b) 是这个子序列的中位数。
根据排序的定义,可以将后面这个条件转换成「若连续子序列的长度为 (t),则 (b) 是第 (leftlceildfrac{t}{2} ight ceil) 大,也就是说比 (b) 大的数与比 (b) 小的数数量相同」。
这样,我们只需要遍历左端点在 (b) 及其左边,右端点在 (b) 及其右边的连续子序列,用前缀和处理出比 (b) 大和比 (b) 小的数的数量。
复杂度:(mathcal{O}(n^2))。
(100 exttt{pts})
想到了 (60) 分做法,(100) 分也简单了。
预处理出比 (b) 大的数的数量减去比 (b) 小的数的数量的值。如果有两个前缀和和相等,就有一个这样的数列。
易证这个值一定在 ([-n,n]) 的范围内,用一个数组 (cnt_i) 记录下值为 (i) 的前缀和的数量。
处理 (b) 左边时,将左边的前缀和统计进去。处理右边时,计算前缀和 (S_i) 并让 (ansleftarrow ans+cnt_{S_i})。
这样就能在 (mathcal{O}(n)) 的时间内完成了。
注意事项
如果你统计左边的前缀和时从前往后统计的,计算右边的答案时 (S_i) 就得是正的,否则 (S_i) 就得是负的,同时右边的前缀和就得从 (b) 开始统计。
Code
#include <cstdio>
using namespace std;
constexpr int max_n = 100000;
int a[max_n], cnt[max_n*2+1]; // 原数组+数量统计
int main()
{
int n, k, ptr, pos = -1, tmp, ans = 0;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) // 读入
{
scanf("%d", a + i);
if (a[i] == k) // 记录位置
pos = i;
}
cnt[max_n]++, tmp = 0;
for (int i = pos - 1; i >= 0; i--) // 统计左边的前缀和
{
tmp += (a[i] > k)? 1:-1; // 计算
cnt[tmp+max_n]++; // 统计上
}
tmp = 0, ans += cnt[max_n];
for (int i = pos + 1; i < n; i++) // 计算答案
{
tmp += (a[i] > k)? -1:1;
ans += cnt[max_n-tmp]; // 我的写法是减去
}
printf("%d
", ans);
return 0; // 然后就 AC 了、
}