USACO历年黄金组真题解析 | 2003年3月

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年黄金组真题解析 | 汇总

---

P10450 Best Cow Fences

【题目来源】

洛谷：[P10450 USACO03MAR] Best Cow Fences G - 洛谷

【题目描述】

给定一个长度为 \(n\) 的非负整数序列 \(A\) ，求一个平均数最大的，长度不小于 \(L\) 的子段。

【输入】

第一行用空格分隔的两个整数 \(n\) 和 \(L\)；

第二行为 \(n\) 个用空格隔开的非负整数，表示 \(A_i\)。

【输出】

输出一个整数，表示这个平均数的 \(1000\) 倍。不用四舍五入，直接输出。

【输入样例】

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

【输出样例】

6500

【算法标签】

《洛谷 P10450 Best Cow Fences》 #动态规划DP# #二分# #前缀和# #USACO# #2003#

【代码详解】

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;  // 定义最大数组长度

int n;                  // 数组长度（元素个数）
int L;                  // 最小子数组长度
int a[N];               // 存储原始数据的数组
double sum[N];          // 前缀和数组（存储a[i]-x的累加和）

/**
 * 检查是否存在长度至少为L的子数组，其平均值大于等于x
 * @param x 要检查的平均值阈值
 * @return 存在满足条件的子数组返回true，否则false
 */
bool check(double x)
{
    // 计算前缀和数组：sum[i] = (a[1]-x) + (a[2]-x) + ... + (a[i]-x)
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i] - x;
    }
    
    double minn = 0;  // 存储前i-L个位置的最小前缀和
    
    // 检查所有长度至少为L的子数组
    for (int i = L; i <= n; i++)
    {
        // 更新前i-L个位置的最小前缀和
        minn = min(minn, sum[i - L]);
        
        // 如果当前前缀和减去最小前缀和≥0，说明存在满足条件的子数组
        if (sum[i] - minn >= 0)
        {
            return true;
        }
    }
    
    return false;
}

int main()
{
    // 输入数组长度和最小子数组长度
    cin >> n >> L;
    
    // 输入数组元素
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    
    // 二分查找的左右边界
    double l = 0, r = 2000, mid;
    
    // 二分查找最大平均值，精度控制到1e-5
    while (r - l > 1e-5)
    {
        mid = (l + r) / 2;
        
        // 检查是否存在平均值≥mid的子数组
        if (check(mid))
        {
            l = mid;  // 平均值可以更大，向右搜索
        }
        else
        {
            r = mid;  // 平均值过大，向左搜索
        }
    }
    
    // 输出结果（乘以1000后取整）
    cout << (int)(r * 1000);
    
    return 0;
}

【运行结果】

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