Best Cow Fences C++题解

Time limit1000 ms; Memory limit30000 kB

描述

Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.

FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input.

Calculate the fence placement that maximizes the average, given the constraint.

输入

• Line 1: Two space-separated integers, N and F.

• Lines 2…N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

输出

• Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields.

样例输入

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

样例输出

6500

思路

题意就是给你一些数让你找出个数不少于F的连续的一段使之平均值最大
枚举会超时，时间复杂度为O(n)才行

假如有
10 6
4
2
1000
10
3
8
5
9
800
6
此时明显是第三个到第九个这一段平均值最大，结合代码不难理解当平均值取262时，min_val会停留在前两个，ans会停留在前九个

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double a[100001], b[100001], sum[100001];
int main() {
	//freopen("input.txt", "r", stdin);
	int N, F;
	cin >> N >> F;
	for (int i = 1; i <= N; i++) scanf("%lf", &a[i]);
	double eps = 1e-5;
	double l = -1e6, r = 1e6;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		for (int i = 1; i <= N; i++) b[i] = a[i] - mid;
		for (int i = 1; i <= N; i++)
			sum[i] = (sum[i - 1] + b[i]);
		double ans = -1e10;
		double min_val = 1e10;
		for (int i = F; i <= N; i++) {
			min_val = min(min_val, sum[i - F]);
			ans = max(ans, sum[i] - min_val);
		}
		if (ans >= 0) l = mid; else r = mid;
		cout << mid << endl;
	}
	cout << int(r * 1000) << endl;
}

也看了一些题解，觉得这个有点意思
本人也是新手，也是在学习中，勿喷

转载请注明出处

欢迎有问题的小伙伴一起交流哦~