首页 > 代码库 > POJ2018 Best Cow Fences

POJ2018 Best Cow Fences

2024-11-19 06:50:38   202人阅读

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.

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 66 4210385941

Sample Output

6500

Source

USACO 2003 March Green
 
【题解】
　　这是一道极其恶心的卡精度题，据说有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 }
POJ2018 Best Cow Fences

 

POJ2018 Best Cow Fences


联系
我们