P1419——寻找段落（洛谷）

题目详情

寻找段落

题目描述

给定一个长度为 $n$ 的序列 $a$，定义 $a_i$ 为第 $i$ 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 $[S,T]$ 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行两个整数 $S$ 和 $T$，表示段落长度的范围，在 $[S,T]$ 之间。

第三行到第 $n+2$ 行，每行一个整数表示每个元素的价值指数。

输出格式

一个实数，保留 $3$ 位小数，表示最优段落的平均值。

样例 #1

样例输入 #1

3
2 2
3
-1
2

样例输出 #1

1.000

提示

【数据范围】

对于 $30\%$ 的数据有 $n\le 1000$。

对于 $100\%$ 的数据有 $1\le n\le 100000$，$1\le S\le T\le n$，$-{10}^4\le a_i\le {10}^4$。

【题目来源】

tinylic 改编

解题思路

题目中告诉我们段落的定义是在[S,T]区间的可变部分，因为是一个区间，可以联想到滑动窗口，单调队列维护区间内容等问题，但是本题的区间范围并不是定长，所以更适合使用单调队列来维护区间单调性。

本题需要考虑前缀和的处理方法，因为区间是连续的，想要获得某一段区间内容的和，只需要sum[i]-sum[i-t];——i为一段区间的结尾，t为一段区间开头的前一个元素。

• 求解这道题的一个关键知识就是：
  一个数组的平均值一定位于数组[最小值，最大值]的区间内，且数组中任意一段连续的序列的平均值都不会超过这个区间。 知道了这一点后，我们再来看题目要求输出的段落的平均值（ 等于 段落总价值 除以 段落长度），是不是也一定位于数组[最小值，最大值]的区间内呢。由此，我们便找到了关键的二分法的区间，即[最小值，最大值]，段落的最大平均值一定位于这个区间内。

• 解题技巧：

sum[i]=sum[i-1]+a[i]-mid;

这是前缀和的计算公式，为什么要减去一个mid呢？
mid作为当前被假设的段落平均值的最大值，
——>这时候又涉及到了一个知识，当一个数组中的每个元素，都减去他的平均值后求和，得到的结果一定大于或者等于0。
前缀和的计算公式就是基于这样的原理：
1.sum[i]-sum[q.front()]>=0时，说明mid值刚好或者过小，需要再向右区间寻找。
2.sum[i]-sum[q.front()]<0时，说明mid值过大，需要再向左区间寻找。

单调队列的使用

单调队列维护了一个长度区间在[S,T]内的段落价值和的单调性，在编写单调队列的代码时，我们要确定好两点：
1.单调队列的单调性：单调队列到底是单增还是单减呢？ 以本题为例——>本题要求找平均值最大的段落，通过前缀和如何表示平均值最大的段落呢？那么就是当前1~i 的前缀和，减去1~i-T 或者 1~i-S 的前缀和以后的最大情况，显然1~i 的前缀和在当前情况下是一定的，那么1~i-T 或者1~i-S 的前缀和哪一个最小，1~i 的前缀和减去它的值就最大
——>由此我们分析得出了，单调队列的单调性应该是单调递增的。
**2.**单调队列维护的区间范围控制，单调队列维护的区间应该在[S,T]之间，所以我们应该判断，当 q.front()<i-T时，表明队列头存储的前缀和已经超出了现区间范围，应该丢弃。

全部代码

#include <bits/stdc++.h>
using namespace std;
double a[100005];
double sum[100005];
int s;
int t;
int n;
double maxv = INT_MIN;
double minv = INT_MAX;
bool check(double mid) {
   
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + a[i] - mid;
	deque<int> q;
	for (int i = 1; i <= n; i++) {
   
		if (i >= s) {
   
			while (!q.empty() && sum[i - s] < sum[q.back()])
				q.pop_back();
			q.push_back(i - s);
		}
		if (!q.empty() && q.front() < i - t)
			q.pop_front();
		if (!q.empty() && sum[i] - sum[q.front()] >= 0)
			return true;
		
		
	}
	return false;
}
int main() {
   
	cin >> n >> s >> t;
	for (int i = 1; i <= n; i++) {
   
		cin >> a[i];
		maxv = max(maxv, a[i]);
		minv = min(minv, a[i]);
	}
	double left = minv;
	double right = maxv;
	while (right - left > 1e-4) {
   
		double mid =(right + left) / 2;
		if (check(mid))
			left = mid;
		else
			right = mid;
	}
	printf("%.3lf", left);
	return 0;
}