usaco 2003 月赛 Best Cow Fences & poj2018 题解

转载请注明：http://blog.csdn.net/jiangshibiao/article/details/21963437

【原题】

Description

Input

Output

Sample Input

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

Sample Output

6500

Source

【大意】给出N头牛，每头牛有一个权值。你要选连续的一些牛，而且数量至少是F。求选出的牛的权值最大平均数。输出ans*1000后截尾取整。

【序言】做了这道题，真的是感触良多。

【初步分析】很容易想到是二分来验证答案，而验证过程不易思考。受分数规划的影响，我们可以每次把ai减去二分出来的ans，变成bi数组。如果在b中找到一段长度大于等于F且总和大于等于0的情况，就是可行的。

【再想】因为是“大于等于F”，所以不能用单调队列来做。

我们先考虑“等于F”的情况。自然，这很容易，直接一个for即可。但是有可能我们在某个等于F的情况时，还要向左或向右拓展。为了叙述方便，我们先定为向左拓展。到底要不要拓展取决于左侧是否有大于0的一段。那么思路就来了：我们先用sum[i]表示b中从1到i的总和。等于F的情况时：sum[i+f-1]-sum[i-1]。我们再设一个数组add[i]，表示在i这个点向左最多拓展的总和。那么add[i]=max(add[i-1]+b[i],0)-->什么意思呢？如果向左可以多拓展，就尽量的拓展，否则我们就不拓展。每次更新时就是：sum[i+f-1]-sum[i-1]+add[i-1]。

【再想】然而我有些点一直过不了啊。如果我改成截尾取整，一些点错了；改成四舍五入，另外一些不同的点错了。这一度让我怀疑是否是数据出错了。后来经过研究才发现，二分是有点问题的：设最终答案是10，当前l=9.9，r=10。自然，l是不会等于10的，而是越来越接近。但是在返回的时候，我们不一定是10，而是9.99999999999。结果截尾取整后，答案就会变成9了。

【改进】也算是“打点”吧，我在二分时返回r值就过了。但这不是完美的解决啊。询问了RZZ大牛：原来，我们可以把结果加上0.0000000001，然后二分再开大精度即可。（当然你得事先想到这种可能）

【代码】

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=100005;
int n,f,i,Min,Max,a[maxn],cnt;
double ans,b[maxn],sum[maxn],add[maxn];
bool check(double p)
{
  int i;
  for (i=1;i<=n;i++) b[i]=a[i]-p;
  for (i=1;i<=n;i++) 
  {
    add[i]=add[i-1]+b[i];if (add[i]<0) add[i]=0;
    sum[i]=sum[i-1]+b[i];
  }
  for (i=1;i<=n-f+1;i++)
    if (sum[i+f-1]-sum[i-1]+add[i-1]>=0) return true;
  return false;
}
double erfen(double l,double r)
{
  double mid=(l+r)/2;
  if (r-l<=0.0001) return r;
  if (check(mid)) 
    return erfen(mid,r);
  return erfen(l,mid);
} 
int main()
{
  freopen("cowfnc.in","r",stdin);
  freopen("cowfnc.out","w",stdout);
  scanf("%d%d",&n,&f);
  for (i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
    Min=min(Min,a[i]);
    Max=max(Max,a[i]);
  } 
  ans=erfen(Min,Max)*1000;
  printf("%d",int(ans));
  return 0;
}

usaco 2003 月赛 Best Cow Fences & poj2018 题解,布布扣,bubuko.com

usaco 2003 月赛 Best Cow Fences & poj2018 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/21963437