Best Cow Fences

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1016 字

二分平均值，前缀和判断是否存在长子段

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1434
// 题意：给定长度为 n 的正整数序列，求平均数最大且长度不小于 L 的连续子段，输出平均值的 1000 倍（直接取整）。
// 思路：二分平均值 + 前缀和判定。
// 1. 把每个数减掉二分的平均数 x，问题变成「是否存在长度不小于 L 的子段和非负」。
// 2. 用前缀和 sum[i]，枚举右端点 i，维护 i - L 之前的最小前缀和作差即可 O(n) 判定。
// 复杂度：O(n log V) 时间 / O(n) 空间
// 易错点：输出是答案乘 1000 后向下取整，不四舍五入，直接强转 int 即可。
// 易错点：判定要用 double，并且二分次数要足够多（60 次以上），否则精度不够会掉 1 分。
#include <bits/stdc++.h>
using namespace std;
int n, L;
vector<double> a, sum;
bool ok(double x){
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i] - x;
    double mn = 0;
    for(int i = L; i <= n; i++){
        mn = min(mn, sum[i - L]);
        if(sum[i] - mn >= 0) return true;
    }
    return false;
}
int main(){
    if(!(cin >> n >> L)) return 0;
    a.assign(n + 1, 0);
    sum.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) cin >> a[i];
    double l = 0, r = 1e9;
    for(int it = 0; it < 80; it++){
        double mid = (l + r) / 2;
        if(ok(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1000) << "\n";
    return 0;
}

Best Cow Fences

正文

一本通·提高篇的其它内容