ZZSR#1完美计算 0/1分数规划题解

蒟蒻脑子不聪明，只会0/1分数规划。
由于我们不会数论，所以这个式子看起来只像0/1分数规划。
上面的项就是普通平方和，下面是平方差，由于平方可表示为若干递增 $2i+1$ 之和，可以用差分的技巧将每个 $b_i$ 设为 $2i+1$ ，然后求最大值。但是不可以排序，因为区间要求连续，可以对 $y_i$ 进行前缀和操作转化为 $c_i$。依旧得如下式，即 $mid$ 满足的条件：

$$max{\sum_{i=l}^{r} (a_i-xb_i)s_i}\geq 0$$

如何求？只需要一个区间满足条件就行了，如果枚举的话一次二分需要 $O(N^2)$ 的时间复杂度，但是我们可以运用贪心思想，为了让算出来的区间值最大，对于每个 $r$ ，应当使其 $l$ 最小，因此我们计算出 $r$ 最小的 $c_i$ 记为 $minn$ 并计算 $c_r-c_{minn}$ 就是以 $r$ 为右端点的最大区间和了。如果最大区间和大于等于0，return 1.
求最小也可以用相同方法贪心取得，只用求左端点最大值即可。
闲话：当初以为比赛很难做完 T3 看了一眼 T4 就交卷了导致没拿到 rk.1

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
double c[100005];
double l=1e18,r=-1e18,L=1e18,R=-1e18;
struct xyl{int a,b;double y;}p[100005];
bool check1(double x){
    double minn=0;
    for(int i=1;i<=n;++i){
        p[i].y=p[i].a*1.0-x*p[i].b,c[i]=c[i-1]+p[i].y;
        if(c[i]-minn>0.0000001)return 1;
        minn=min(minn,c[i]);
    }
    return 0;
}
bool check2(double x){
    double maxn=0;
    for(int i=1;i<=n;++i){
        p[i].y=p[i].a*1.0-x*p[i].b,c[i]=c[i-1]+p[i].y;
        if(c[i]-maxn<-0.0000001)return 1;
        maxn=max(maxn,c[i]);
    }
    return 0;
}
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)p[i]={read(),2*i-1,0},p[i].a*=p[i].a,r=max(r,1.0*p[i].a/p[i].b+0.5),l=min(l,1.0*p[i].a/p[i].b-0.5);
    L=l,R=r;
    for(int i=1;i<=50;++i){
        double mid=l+(r-l)/2;
        if(check1(mid))l=mid;
        else r=mid;
    }
    printf("%.3f ",l);
    l=L,r=R;
    for(int i=1;i<=50;++i){
        double mid=l+(r-l)/2;
        if(check2(mid))r=mid;
        else l=mid;
    }
    printf("%.3f",r);
    return 0;
}