题解 | #[CQOI2009]中位数图#

[CQOI2009]中位数图

题目描述:

给出 1 ~ n（ n ≤ 100000 ）的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 b （ 1 ≤ b ≤ n ）。中位数是指把所有元素从小到大排列后，位于中间的数。

输入描述:

第一行为两个正整数n和b ，第二行为1~n 的排列。

输出描述:

输出一个整数，即中位数为b的连续子序列个数。

做这道题之前可以先做 校门外的树 领会一下前缀和&差分的思想~ 看着大佬们的答案想了很久，终于找到了一个看起来更加优雅的方法。

首先考虑暴力，枚举子串的复杂度O(n^2)，排列子串的复杂度O(nlogn),总复杂度O(n^3 logn)，对一道数据量1e5的题目来说是不能接受的。但如果只需要枚举每个子串，然后在O(1)内判断子串是否符合条件并计数，总复杂度就能降低到O(n^2)了。

所以本题基本还是依照大佬们的判断思路：满足条件的子串中大于中位数的数等于小于中位数的数。具体步骤如下：

1. 可以将数组中大于中位数的数设置为1，小于的设置为-1，标记中位数下标，如下：

 for (i = 0; i < n; i++)
{
	if (num[i] > b)
		num[i] = 1;
	else if (num[i] < b)
		num[i] = -1;
	else
		num[i] = 0, k = i;
}

2-(1). 设prevSum[i]是不包括num[i]的前缀和，hereSum[i]就是包括num[i]的前缀和。满足条件的、包含num[k]的字串num[i] + num[i + 1] + ... + num[j] == 0, 所以hereSum[j] - prevSum[i] == 0，如图：

//    i                 0   1   2   3   4   5   6 ...
//   num[i]             1  -1   1   1   0  -1  -1
//  prev[i]           [ 0   1   0 ] 1   2   2   1
//  here[i]           [ 1   0   1   2   2   1   0 ]
//  here[i]-prev[i]           [                   ]

2-(2). 我们对中位数每个左边的数（子串开头）枚举中位数右边的数（子串结尾），本题复杂度最高的部分，但系数较小所以还算可以接受。为什么不用prev[i] - prev[j]呢，主要是为了统一操作。

int ans = 0;
for (i = 0; i <= k; i++)
	for (j = k; j < n; j++)
		if (hereSum[j] - prevSum[i] == 0)
			ans++;

3. 那么 代价是什么呢？代价是多消耗了一半的空间......只好捏着鼻子用指针操作了，这里是核心算法的初始环节：

int* prevSum = new int[n], * hereSum = new int[n];
	prevSum[0] = 0;
	for (i = 1; i < n; i++)
		prevSum[i] = prevSum[i - 1] + num[i - 1];
	hereSum[0] = num[0];
	for (i = 1; i < n; i++)
		hereSum[i] = hereSum[i - 1] + num[i];

4. 模块化后再处理一下输入输出，恭喜你得到了AC代码：

#include<iostream>
using namespace std;
int medianPlot(int* num, int n, int b)
{
	int i, j, k;
	for (i = 0; i < n; i++)
	{
		if (num[i] > b)
			num[i] = 1;
		else if (num[i] < b)
			num[i] = -1;
		else
			num[i] = 0, k = i;
	}

	int* prevSum = new int[n], * hereSum = new int[n];
	prevSum[0] = 0;
	for (i = 1; i < n; i++)
		prevSum[i] = prevSum[i - 1] + num[i - 1];
	hereSum[0] = num[0];
	for (i = 1; i < n; i++)
		hereSum[i] = hereSum[i - 1] + num[i];

	int ans = 0;
	for (i = 0; i <= k; i++)
		for (j = k; j < n; j++)
			if (hereSum[j] - prevSum[i] == 0)
				ans++;

	delete[] prevSum;
	delete[] hereSum;
	return ans;
}

int main(void)
{
	int n, b;
	cin >> n >> b;

	int* num = new int[n];
	for (int i = 0; i < n; i++)
		cin >> num[i];
	cout << medianPlot(num, n, b);

	delete[] num;
	return 0;
}

结尾多废话两句，我们的追求不应该只是停留在过关这个层面，而应该是可读性、可维护性，总而言之，突出一个优雅。如果放弃了对优雅的追求，debug环节的效率可能反而更低呢？

这篇题解还很笨拙，如果有更好更优雅的解法欢迎分享！

复杂度分析：时间复杂度O(n^2)，空间复杂度O(n)。