【题解】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

#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$

于是得到以下代码:

#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 啦~

【题解】POJ2018 Best Cow Fences
本文作者:
Hans362
最后更新
2020-05-05
许可协议
转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

评论

您所在的地区可能无法访问 Disqus 评论系统,请切换网络环境再尝试。