Best Cow Fences
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 11175 | Accepted: 3666 |
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.
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.
* 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
Source
【题解】
这是一道极其恶心的卡精度题，据说有O(n)做法，但太高端了。
nlogn做法很显然是二分答案，关键就在如何检查了。
直接去求平均值是否大于某个数跟暴力无异，因此我们转换一下，把每个数都减去答案，求一个满足条件的区间且区间和大于0。
预处理dp[i]表示i及i向右的区间最大是多少，可以不选，为0。
线性做就可以了
放大处理，被卡了老半天精度，最终弃疗，老老实实乘了1ex
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 7 inline void read(long long &x) 8 { 9 x = 0;char ch = getchar(),c = ch; 10 while(ch < '0' || ch > '9')c = ch, ch = getchar(); 11 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 12 if(c == '-')x = -x; 13 } 14 15 const int MAXN = 100000 + 10; 16 17 long long n,num[MAXN],len,sum,tmp[MAXN],dp[MAXN]; 18 19 int check(long long m) 20 { 21 for(register int i = 1;i <= n;++ i) 22 tmp[i] = num[i] - m; 23 //dp[i]表示从i开始向右的最大和 24 for(register int i = n;i >= 1;-- i) 25 if(dp[i + 1] + tmp[i] > 0)dp[i] = dp[i + 1] + tmp[i]; 26 else dp[i] = 0; 27 for(register int i = 1;i <= n;++ i) 28 tmp[i] += tmp[i - 1]; 29 //最短长度len + 向右最大和 30 for(register int i = len;i <= n;++ i) 31 if(tmp[i] - tmp[i - len] + dp[i + 1] >= 0) 32 return 1; 33 return 0; 34 } 35 36 int main() 37 { 38 read(n), read(len); 39 for(register int i = 1;i <= n;++ i) 40 read(num[i]), num[i] *= 10000000, sum += num[i]; 41 register long long l = 1, r = sum, mid, ans; 42 while(l <= r) 43 { 44 mid = (l + r) >> 1; 45 if(check(mid)) l = mid + 1; 46 else r = mid - 1; 47 } 48 printf("%lld", l/10000); 49 return 0; 50 }