题解：P10450 [USACO03MAR] Best Cow Fences G

题目链接

O(n^3) 做法

直接暴力枚举长度、起点，再全部跑一边求平均数。

附上我丑陋的代码和提交记录，这个代码可以得42分。

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

const int NR = 1e5 + 5;
long long n, l, a[NR], sum, ave;

int main() {
	cin >> n >> l;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = l; i <= n; i++) //先枚举长度
		for (int j = 1; j <= n - i + 1; j++) { //枚举起点
			sum = 0;
			for (int k = j; k <= j + i - 1; k++)//遍历，求和
				sum += a[k];
			ave = max(ave, sum * 1000 / i);
		}
	cout << ave;
	return 0;
}

O(n^2) 做法

根据上面，我们可以发现求和的那段过程可以用前缀和优化，我们可以先 $ O(n) $ 预处理前缀和，再枚举。

下面是我丑陋的代码和提交记录，我们已经可以拿到70分了。

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

const int NR = 1e5 + 5;
long long n, l, a[NR], s[NR], sum, ave;

int main() {
	cin >> n >> l;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];//前缀和预处理 
	for (int i = l; i <= n; i++) //同上，先枚举长度
		for (int j = 1; j <= n - i + 1; j++) { //枚举起点
			sum = s[j + i - 1] - s[j - 1];
			ave = max(ave, sum / i * 1000);
		}
	cout << ave;
	return 0;
}

O(n log W) 做法

我们可以发现这道题平均数越小越容易达到，符合二分的特点，所以我们可以用二分优化。

历尽千辛万苦，我们AC了这道题，再次贴上我丑陋的代码和提交记录。

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

const int NR = 1e5 + 5;
long long n, L;
double l = 0, r = 2e3, s[NR], a[NR];//s[i]表示从a[1]加到a[i]的总和与理想的总和的差

bool check(double mid) {
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] - mid; 
	double minn = 0;
	for (int i = L; i <= n; i++) {//枚举起点
		minn = min(minn, s[i - L]);//累求最小值 
		if(s[i] - minn >= 0)
			return 1; 
	}
	return 0;
}

int main() {
	cin >> n >> L;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (r - l > 1e-5) {
		double mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	cout << int(r * 1000);
	return 0;
}