【题解】POJ2018 Best Cow Fences

2020-05-05 OI 笔记

文章目录

题目
开工！
还没完呢

本文最后更新于天前，文中部分描述可能已经过时。

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

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

题目

原题是 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;
}