【题解】POJ2018 Best Cow Fences

最近终于开始学《提高篇》了…然后就刷到了这一题…

《提高篇》书上写的这道题的思路说实话我看了很久都不太能理解(当然现在明白了),所以就以我的角度来谈谈这道题该怎么下手做出正解~

题目

原题是 POJ2018 但是好像也是从 USACO 搬运过来的?

http://poj.org/problem?id=2018

同时附上一个翻译过的版本:

https://oj.hans362.cn/problem/5

需要注意的是,本题在2018年第一次印刷的《提高篇》书上题干表述有误,“子序列”应更改为“子串”才对

开工!

首先呢,这道题是一道二分答案,因为它符合求最小值的最大值这种问题模式

那么二分答案要做的第一件事就是确定答案的范围,在本题中需要求解的是最大的平均数,按理来说是有一个范围的,但是其实没必要求得那么精确,咱就简单粗暴一点把答案范围定在 $[-10^6,10^6]$,反正精确范围肯定是这个范围的子集

紧接着由于答案是平均数,产生小数是很自然的,因此要选择实数域上的二分

考虑到最后题目让我们输出的是最大平均数的 $1000$ 倍,因此设置精度 $eps = 1*10^{-5}$

然后就开始设计二分判定,众所周知二分是把求解转化为判定的一种思想,本题中我们需要判定的是“是否存在一个长度不小于 $L$ 的子串,且该子串平均数不小于二分的值”

为了便于操作按照惯用套路咱把数列 $A$ 中每一项都减去二分的值,运用化归思想将问题转化为判定“是否存在一个长度不小于 $L$ 的子串,且该子串的和非负”

由于是存在性问题(区别于恒成立问题),只需要保证数列 $A$ 中所有长度不小于 $L$ 的子串的子串和中的最大值非负即可,注意到求和是一个很浪费时间的过程,所以我们就把它用前缀和的方式预处理掉

学过数列的同学们应该不难理解,假设数列 $A$ 某一子串为 $A_{j+1},A_{j+2},…,A_i$ ,定义 $S_i$ 为数列 $A$ 前 $i$ 项的和,那么

$$该子串的子串和 = A_{j+1}+A_{j+2}+…+A_i = S_i - S_j $$

那么最后一个问题,怎么遍历数列 $A$ 中所有长度不小于 $L$ 的子串呢?这个容易呀~$i: L → n, j: 0 → i-L$ 循环嵌套一下就搞定

最后得到如下代码:(注释写得挺详细的应该看得懂吧w

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
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 1;

int n;
double a[MAXN]; //原始数列 A
double b[MAXN]; //数列 A 中每个数都减去二分平均数得到的新数列
double s[MAXN]; //前缀和
int L;

int main() {
cin >> n;
cin >> L;
for (int i = 1; i <= n; i++) cin >> a[i];
double eps = 1e-5; //设置精度为10^{-5}
//显然答案应该落在-1e6~1e6
double l = -1e6;
double r = 1e6;
while (r - l > eps) { //控制精度
double mid = (l + r) / 2;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - mid; //把 A 数列中每个数都减去二分平均数
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + b[i]; //递推求前缀和
}
//开始判定
double ans = -1e10; //初始化数列 A 中所有长度不小于 L 的子串的子串和中的最大值为一个很小很小的数
//遍历所有长度不小于 L 的子串
for (int i = L; i <= n; i++) {
for (int j = 0; j <= i - L; j++) {
ans = max(ans, s[i] - s[j]); //不断更新最大值
}
}
if (ans >= 0) //如果最大值非负,那么存在,于是更新左端点,在二分点的右侧继续寻找
l = mid;
else //如果最大值都是负的,那么彻底没戏,不存在,于是更新右端点,在二分点的左侧继续寻找
r = mid;
}
cout << (int)(r * 1000) << endl; //输出结果,别忘了题目要求的乘以1000
return 0;
}

还没完呢

如果你真的按照上面我说的去做了,那么你大概会得到 57 分,并且发现过不了的点都是 TLE

(什么!你 AC 了?!要么数据太水要么你不是这样做的)

虽然总比爆零要好,但是咱要追求完美怎么能罢休~

分析一下,上面算法中可以优化的应该就是那个两重循环了,我们粗略地把判定时间复杂度看成 $O(N^2)$ (但是实际上应该比 $O(N^2)$ 要好一点),那么有没有 $O(N)$ 的判定方法呢?

我们又回到了这个问题:怎么优雅地遍历数列 $A$ 中所有长度不小于 $L$ 的子串呢?难道真的需要两重循环吗?

前面提到过,假设数列 $A$ 某一子串为 $A_{j+1},A_{j+2},…,A_i$ ,定义 $S_i$ 为数列 $A$ 前 $i$ 项的和,那么

$$该子串的子串和 = A_{j+1}+A_{j+2}+…+A_i = S_i - S_j $$

当 $i$ 取某个值时,观察上面的式子,发现 $S_i$ 为定值,$S_{j}$ 随 $j$ 可变,因为要求最大的子串和,所以减数 $S_{j}$ 越小越好

当 $i$ 每次增加 $1$,即 $i$ 变成 $i+1$ 那么 $j$ 的取值范围会由 $[0,i-L]$ 变到 $[0,i+1-L]$ 仔细观察发现 $j$ 可取的值只多了一个

所以我们完全没有必要对 $j$ 做循环,我们只需要在 $i$ 的每一次循环中记录下当前的 $S_{j}$ 并和上一轮最小值 $tmp_min$ 取较小的那个存入 $tmp_min$

于是得到以下代码:

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
41
42
43
44
45
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 1;

int n;
double a[MAXN]; //原始数列 A
double b[MAXN]; //数列 A 中每个数都减去二分平均数得到的新数列
double s[MAXN]; //前缀和
int L;

int main() {
cin >> n;
cin >> L;
for (int i = 1; i <= n; i++) cin >> a[i];
double eps = 1e-5; //设置精度为10^{-5}
//显然答案应该落在-1e6~1e6
double l = -1e6;
double r = 1e6;
while (r - l > eps) { //控制精度
double mid = (l + r) / 2;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - mid; //把 A 数列中每个数都减去二分平均数
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + b[i]; //递推求前缀和
}
//开始判定
double ans = -1e10; //初始化数列 A 中所有长度不小于 L 的子串的子串和中的最大值为一个很小很小的数
double tmp_min = 1e10; //初始化上一轮最小值为一个很大很大的数
//遍历所有长度不小于 L 的子串
for (int i = L; i <= n; i++)
{
tmp_min = min(tmp_min, s[i - L]); //刷新最小值
ans = max(ans, s[i] - tmp_min); //不断更新最大值
}
if (ans >= 0) //如果最大值非负,那么存在,于是更新左端点,在二分点的右侧继续寻找
l = mid;
else //如果最大值都是负的,那么彻底没戏,不存在,于是更新右端点,在二分点的左侧继续寻找
r = mid;
}
cout << (int)(r * 1000) << endl; //输出结果,别忘了题目要求的乘以1000
return 0;
}

然后就可以 AC 啦~



评论

如果您看不见评论框,八成是因为您还未接入真正意义上自由开放的互联网哟~自己看着办吧~

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×