POJ Best Cow Fences

POJ Best Cow Fences

题目:

  • 原题是英文。题目大意如下:给定正整数数列A,求一个平均数最大的、长度不小于L的子段

题解:

  • 二分答案。(妙题)
  • 因为如果一个平均数可以满足,那么比它小的平均数就不考虑了,只用考虑是否可以满足更大的平均数。
  • 但是如何check呢?
  • 将数列中每一个数减去二分的值,那么问题转换为判定:“是否存在一个长度>=L的子段和为非负”
  • 可以这样考虑:
  • 记sum为前缀和,i < j。
  • 当i = L时,j的取值范围是1(sum[L] - sum[1 - 1])
  • 当i = L + 1时,j的取值范围是1-2
  • 当i = L + 2时,j的取值范围是2-3
  • ... ...
  • 发现每当i+1,j的范围也+了一个1。又因为i的sum是固定的,为了使sum[i] - sum[j - 1]尽可能大,所以sum[j - 1]要尽可能小。所以用一个变量记录当前所有sum[j - 1]里的最小值既可。然后在过程中记录子段和最大值ans。for完之后看看ans是否>=0
  • 另:这是道带小数的二分题,而且没有给出精度。对于此类题目,可以固定二分次数,这也是一种相当不错的策略。
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 100005
using namespace std;

int n, L;
double l = 1e9, r = -1e9, ans;
double a[N], b[N], sum[N];

int read()
{
    int x = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x;
}

bool check(double val)
{
    for(int i = 1; i <= n; i++)
        b[i] = a[i] - val,
        sum[i] = sum[i - 1] + b[i];
    double minn = 1e9, ans = -1e9;
    for(int i = L; i <= n; i++)
    {
        minn = min(minn, sum[i - L]);
        ans = max(ans, sum[i] - minn);  
    }
    return ans >= -1e-6; //这题卡精度
}

int main()
{
    freopen("P2018.in", "r", stdin);
    freopen("P2018.out", "w", stdout);
    
    cin >> n >> L;
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        l = min(l, a[i]);
        r = max(r, a[i]);
    }
    for(int i = 1; i <= 60; i++)
    {
        double mid = (l + r) / 2.0;
        if(check(mid)) l = mid, ans = mid;
        else r = mid;
    }
    cout << (int)(ans * 1000.0);
    return 0;
}
上一篇:骑马修栅栏 Riding the Fences


下一篇:(二)ECMA 335 解析 /ECMA 334