Best Cow Fences

poj 2018

題目大意：

給出一個(gè)正整數(shù)數(shù)列，要你求平均數(shù)最大，長(zhǎng)度不小于M的字串，結(jié)果乘1000取整

輸入樣例

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

輸出樣例

6500

數(shù)據(jù)范圍

$1?N?100,000$

解題思路：

我們先想一想，如何求一個(gè)長(zhǎng)度不小于M且和最大的字段，我們可以設(shè)兩個(gè)值num和minn分別表示結(jié)果和前面減去的最小值
我們圖文結(jié)合（如下圖，當(dāng)n為5，M為2）
我們先枚舉i（從m到n），表示當(dāng)前字段的結(jié)尾位置，因?yàn)殚L(zhǎng)度不能小于M，所以紅色部分是必須選的，然后前面的黃色部分是可選可不選的，我們到每一個(gè)位置時(shí)就更新一遍，就相當(dāng)于求一個(gè)和最小的字段，然后到時(shí)直接用sum[i]（前綴和）減去它，就可以更新num了

因?yàn)樗蟮氖瞧骄底畲蟮?#xff0c;所以我們每次把所有數(shù)減去我們二分得到的結(jié)果，然后看一看所得的num是否是非負(fù)數(shù)，如果是就說(shuō)明可以找到這樣的一個(gè)字段，否則沒有

代碼：

#include<cstdio> #define min(a,b) (a)<(b)?(a):(b) #define max(a,b) (a)>(b)?(a):(b) using namespace std; int n,m; double l,r,mid,num,minn,a[100500],sum[100500]; int main() {scanf("%d %d",&n,&m);for(int i=1;i<=n;++i)scanf("%lf",&a[i]);l=-1e6;r=1e6;while(r-l>1e-5){mid=(l+r)/2;//二分for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i]-mid;//求前綴和num=-1e10;minn=1e10;for(int i=m;i<=n;++i){minn=min(minn,sum[i-m]);//計(jì)算減去的最小是多少num=max(num,sum[i]-minn);//計(jì)算結(jié)果}if(num>=0) l=mid;//判斷是否存在else r=mid;}printf("%d",(int)(r*1000)); }

總結(jié)

以上是生活随笔為你收集整理的【二分】Best Cow Fences（poj 2018）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。