usaco 2003 月賽 Best Cow Fences & poj2018 題解

轉載請注明：http://blog.csdn.net/jiangshibiao/article/details/21963437

【原題】

Best Cow Fences

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 9137	Accepted: 2919

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
      

Source

USACO 2003 March Green

【大意】給出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;
}