rt

题面： 代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int s,t;
    double a,b;
}pt[100005];
int n,t;
double dp[100005],suma=0,sumb=0;
bool cmp(node x,node y){
    return x.s>y.s;
}
bool check(double x){
    //判断只选 mid*Σb-Σa>=0 能否成功
    double sum=0;
    int maxt=0;
    for(int i=1;i<=n;i++){
        if(x*pt[i].b-pt[i].a>=0){
            sum+=x*pt[i].b-pt[i].a;
            if(maxt>=pt[i].s-1)maxt=max(maxt,pt[i].t);
        }
    }
    //如果不能，dp判断能否通过选某些额外服务器使其成功且<sum
    if(maxt==t)return 1;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        double mn=1e9;
        for(int j=1;j<i;j++){
            if(pt[j].t>=pt[i].s-1)mn=min(dp[pt[j].t],mn);
        }
        if(maxt>=pt[i].s-1)mn=min(mn,0.0);
        if(pt[i].b*x-pt[i].a>=0)dp[pt[i].t]=max(dp[pt[i].t],mn);
        else dp[pt[i].t]=max(dp[pt[i].t],mn-pt[i].b*x+pt[i].a);
    }
    cout<<x<<" ";
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<" ";
    }
    cout<<endl;
    return dp[t]<=sum;
}
int main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>pt[i].s>>pt[i].t>>pt[i].a>>pt[i].b;
        suma+=pt[i].a;
        sumb+=pt[i].b;
    }
    // sort(pt+1,pt+1+n,cmp);
    double l=1,r=1005;
    while(r-l>1e-4){
        double mid=(l+r)/2.0;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.3f",r);
    system("pause");
    return 0;
}
//from chpyx2
/*
    mid*Σb-Σa>=0
*/