最佳牛围栏

发表于 | 分类于 |

问题

农夫约翰的农场由N块田地组成，每块地里都有一定数量的牛，其数量不会少于1头，也不会超过2000头。约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。围起区域内至少需要包含F块地，其中F会在输入中给出。在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 N 和 F ，数据间用空格隔开。
接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第i片区域内包含的牛的数目。

输出格式

输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。

输入样例

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例

6500

思路

题目为最大值问题。由于最大值具有单调性，可通过二分答案转为判定的技巧，得到最大值。该技巧通常用于直接求最优解比较困难的情况。

二分特征词：“最大值最小” or “最小值最大”和数列具有单调性(可排序）

由于区间长度大于等于f，故求sum[i-f]的最小值。减平均值mid将区间和转化为非负区间的问题。只要存在非负区间和，则表明该mid值能取到。利用变量ans保存最大区间和，判定ans大于等于0的情况，确定该mid值是否可取。

代码

知识积累

实数域上的二分：保留k位数，精度一般设为1e-(k+2)。根据目标值与mid的关系，确定更新l或者r。

while (l + 1e-5 < r) //1e-5由精度而定
{
    double mid = (l + r) / 2;
    if (check(mid)) l = mid; else r = mid; //存在非负区间和，目标值在mid的右侧
}

定义为常数：const int N = 100010;
由输入数据确定区间： double l = 0, r = maxVal;
数组也可进行区间迭代：for (auto u:a);
减平均值mid将区间和转化为非负区间的问题：for (int i = 1; i <= n; i++) sum[i] = cow[i] - mid;
前缀和序列，下标从1开始：for (int i = 1; i <= n; i++) sum[i] += sum[i-1];

最大最小值的初始值：交叉赋值，最大赋最小，最小赋最大。

double minVal = 1e10; //初始化为最大值
double ans = -1e-10; //最大区间和,初始化为最小负数

i从f开始遍历，保证下标i-f大于0：sum[i-f]

调试过程

最大最小值的初始值设定
存在非负区间和，目标值在mid的右侧，l=mid
结果转为整数 cout << int(r * 1000) << endl;
实数域二分确定取左值还是右值，最大值选取右值

#include <iostream>
using namespace std;

const int N = 100010; //定义为常数
int n, f;
int cow[N]; //下标从1开始
double sum[N]; //double类型,前缀和数组

bool check(double mid)
{
    for (int i = 1; i <= n; i++) sum[i] = cow[i] - mid; //减平均值mid将区间和转化为非负区间的问题
    for (int i = 1; i <= n; i++) sum[i] += sum[i-1]; //前缀和序列

    //调试备注，最大最小值的初始值
    double minVal = 1e10; //初始化为最大值
    double ans = -1e-10; //最大区间和,初始化为最小负数
    for (int i = f; i <= n; i++) //i从f开始遍历,保证下标i-f大于0
    {
        minVal = min(minVal, sum[i-f]); //由于区间长度大于等于f,故求sum[i-f]的最小值
        ans = max(ans, sum[i] - minVal);
    }
    if (ans >= 0) return true; //存在非负区间和
    return false;
}

int main()
{
    int maxVal;
    cin >> n >> f;
    for (int i = 1; i <= n; i++) //下标从1开始
    {
        cin >> cow[i];
        maxVal = max(maxVal, cow[i]);
    }
    double l = 0, r = maxVal; //r最大为max

    //平均值为浮点型,故为实数域上的二分
    while (l + 1e-5 < r) //1e-5由精度而定
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid; else r = mid; //存在非负区间和，目标值在mid的右侧
    }

    //如何确定取左值还是右值,最大值选取右值
    cout << int(r * 1000) << endl; //选取右值结果转为整数
}