Time Limit: 1000MS Memory Limit: 30000K
- Total Submissions: 12144 Accepted: 3958
- Description
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.
Input
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.
Output
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.
- Sample Input
- 10 6
- 6
- 4
- 2
- 10
- 3
- 8
- 5
- 9
- 4
- 1
- Sample Output
- 6500
题意: N, F.n 个数, 求一个长度大于 F 的序列, 平均数最大. 输出平均数乘 1000
思路: 二分答案, 对于 [L,R] 区间中的 mid, 求是否有一个长度大于 F 的序列平均数大于 mid. 来缩小区间
把序列减去 mid, 问题就变成了是否存在一个长度大于 F 的序列, 最大字段和大于零. 没有长度限制, 最大子段和的 DP 问题. 有了长度限制可以转化为前缀和 sum[r] - sum[l - 1] , 我们用前缀和维护一个长度大于 F 的序列, 维护一下前缀和的最小值.
- double ans = -1e9;
- double min_val = 1e9;
- for(int i = L; i <= N; i++ ) {
- min_val = min(min_val, sum[i - L]);
- ans = max(ans, sum[i] - min_val);
- }
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- const int MAXN = 1e5 + 7;
- const double EPS = 1e-5;
- int N, L;
- double a[MAXN], b[MAXN], sum[MAXN];
- int main()
- {
- while(~scanf("%d %d", &N, &L)) {
- for(int i = 1; i <= N;i ++ ) {
- scanf("%lf", &a[i]);
- }
- double l = -1e8, r = 1e8;
- while(l + EPS <r) {
- double mid = (l + r) / 2.0;
- 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 = -1e9;
- double min_val = 1e9;
- for(int i = L; i <= N; i++ ) {
- min_val = min(min_val, sum[i - L]);
- ans = max(ans, sum[i] - min_val);
- }
- if(ans>= 0) {
- l = mid;
- } else {
- r = mid;
- }
- }
- printf("%d\n", int(r * 1000));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2622776.html