AcWing 102. 最佳牛围栏

比较有意思的一道题
总的思路就是二分+前缀和，不难，但是其中有的思想还是有价值的
所以我就主要从这道题入手来浅谈二分中的转化判定问题

思路

如何求一个字段，使和最大且自段长度不超过L

咕咕咕，写不出数学公式来就只贴代码吧

double min_ans=0x3f3f3f,max_ans=-0x3f3f3f;
    for(int i=p; i<=n; ++i) {
        min_ans=min(min_ans,num[i-p]);
        max_ans=max(max_ans,num[i]-min_ans);
    }

核心思路

二分答案转化为判定问题
这是一个很有用的思路，借助二分我们可以吧求最优解的问题转化为给定一个$mid$值
，判定是否存在一个可行方案评分达到$mid$的问题

以后会更新的

代码

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int N=100001;
double a[N],num[N],l,r,b[N];
int n,p;
double max(double x,double y) {
    return x>=y?x:y;
}
double min(double x,double y) {
    return x<=y?x:y;
}
int check(double mid) {
    for(int i=1; i<=n; ++i)
        num[i]=a[i]-mid,num[i]+=num[i-1];   //处理前缀和
    double min_ans=0x3f3f3f,max_ans=-0x3f3f3f;
    for(int i=p; i<=n; ++i) {
        min_ans=min(min_ans,num[i-p]);
        max_ans=max(max_ans,num[i]-min_ans);
    }
    if(max_ans<=0) return 0;
    else return 1;
}
int main() {
    cin>>n>>p;
    for(int i=1; i<=n; ++i) cin>>a[i];
    l=0,r=1000000;
    while(r-l>eps) {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<int(r*1000);
    return 0;
}

最佳牛围栏

原文：https://www.cnblogs.com/pyyyyyy/p/11655846.html