POJ2018:Best Cow Fences 题解

思路

这道题目转换一下题意就可以分析出很多东西。其实这个问题就是在问一个给定的序列之中,求一个平均数最大、长度不少于\(F\)的字串。我们可以尝试考虑二分答案的做法。本题要二分的东西是平均数,而平均数是属于实数范围内的,所以我们必须在实数域中进行二分答案。我们要设定一个精度值为\(eps\),当\(r-l>eps\)时,说明还没有到比较准确的地步,然后继续二分,直到插值小于\(eps\)。

接下来我们来考虑\(check(mid)\)的写法。我们先处理一个\(tmp[]\)数组,来存放每个数与猜测的平均值\(mid\)之差,与此同时计算出这些差值的前缀和。然后开始\(O(n)\)扫描,查找最长的序列。我们可以在扫描过程中记录最小的左端点,然后在每次遍历右端端点时,对两者进行相减,记录最大的,便可找到连续最长的序列。最后,如果最大的答案小于0的话,那么意味着这个答案不合法,需要更小的平均数。反之,则追求更大的平均数。

代码

// POJ2018.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100200;
double seq[maxn], sum[maxn], tmp[maxn];
int N, F;
bool check(double mid)
{
    sum[0] = 0;
    for (int i = 1; i <= N; i++)
        tmp[i] = seq[i] - mid, sum[i] = sum[i - 1] + tmp[i];
    double min_val = 1e10;
    double ans = -1e10;
    for (int i = F; i <= N; i++)
        min_val = min(min_val, sum[i - F]), ans = max(ans, sum[i] - min_val);
    if (ans >= 0)
        return true;
    return false;
}

int main()
{
    scanf("%d%d", &N, &F);
    for (int i = 1; i <= N; i++)
        scanf("%lf", &seq[i]);
    double l = -1e6, r = 1e6, eps = 1e-6;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << (int)(r * 1000) << endl;
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注