欢迎大家订阅我的专栏：算法题解：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-5while (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