【BZOJ】5090[Lydsy1711月赛]组题-01分数规划

题解

二分答案找最小。因为是实数范围，实测50次最佳，100TLE，30WA。

前缀和为s[i],每次O(n)更新一个b[i]数组， b[i]=s[i]−i∗mid b [ i ] = s [ i ] − i ∗ m i d （mid为枚举的平均值），更新的同时记录一下前缀b[i]最小的下标。然后再O(n)check一下，若b[i]-b[mn[i-k]]>0，此时最小值必小于等于当前mid，反之则大于。

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
typedef double db;
typedef long long ll;
const int N=+;

int n,k,a[N],mn[N]; 
ll s[N],A,B,T;db b[N];

inline int rd()
{
    char ch=getchar();int x=,f=;
    while(!isdigit(ch)){if(ch=='-') f=-;ch=getchar();}
    while(isdigit(ch)){x=x*+(ch^);ch=getchar();}
    return x*f;
}

bool check(db mid)
{
    int i,j;b[]=a[]-mid;
    for(i=;i<=n;++i) {b[i]=b[i-]+a[i]-mid;mn[i]= b[i]< b[mn[i-]]? i:mn[i-];}
    for(i=k;i<=n;++i){
        if(b[i]>b[mn[i-k]]){
            A=s[i]-s[mn[i-k]];B=i-mn[i-k];
            return true;
        }
    }
    return false;
}
inline ll gcd(ll x,ll y){return !y? x:gcd(y,x%y);}

int main(){
    int i,j;
    n=rd();k=rd();
    for(i=;i<=n;++i) {a[i]=rd();s[i]=s[i-]+a[i];}
    db l=-,r=,mid;mn[]=;
    for(i=;i<=;++i){
        mid=(l+r)/;
        if(check(mid)) l=mid;
        else r=mid;
    }
    T=gcd(A,B);if(T<) T=-T;
    if(T) A/=T,B/=T;
    printf("%lld/%lld\n",A,B);
}