P14763 [Opoi 2025] CCD 的赌局

考虑枚举 \(k\)，考虑如何计算答案。
对于已经确定的 \(A,B\)，设 \(A=x\),有 \(B=T-x\)。
如果在某个 \(i\) 处，\(A\times a_i\) 更大有 \(x\times a_i\ge (T-x)\times b_i\)，即 \(\frac xT\ge\frac{b_i}{a_i+b_i}\)，按照 \(\frac{b_i}{a_i+b_i}\) 排序，对于一个 \(x\)，满足 \(A\times a_i\) 更大的 \(i\) 一定是一个前缀，可以用离散化+树状数组维护，而整个式子是一个单峰函数，可以三分。由于最小值一定取在某个 \(i\) 的 \(\frac{b_i}{a_i+b_i}\)，所以直接在整数域上三分即可。
时间复杂度 \(\mathcal{O}(\log^2n)\)

代码

/*
Luogu P14763 [Opoi 2025] CCD 的赌局
2026-03-09
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(double&x){scanf("%lf",&x);}
    inline void write(double x){printf("%.2lf",x);}
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=100010;
int n;double T;
class BIT{
private:
    double t[maxn];
    int low(int u){return u&-u;}
public:
    void up(int u,double add){while(u<=n) t[u]+=add,u+=low(u);}
    double query(int u){double ans=0;while(u) ans+=t[u],u-=low(u);return ans;}
    void clear(){memset(t,0,sizeof(t));}
    double query(int l,int r){return query(r)-query(l-1);}
}ta,tb;
struct node{double a,b;int id;}a[maxn],p[maxn];
double pre[maxn];
double calc(int x){
    double z=p[x].b/(p[x].a+p[x].b)*T;
    return z*ta.query(x)+(T-z)*tb.query(x+1,n);
}
signed main(){
    read(n,T);
    for(int i=1;i<=n;i++) read(a[i].a,a[i].b),a[i].id=i,p[i]=a[i];
    sort(p+1,p+1+n,[](node a,node b){return a.b/(a.a+a.b)<b.b/(b.a+b.b);});
    for(int i=1;i<=n;i++) a[p[i].id].id=i;
    for(int i=1;i<=n;i++){
        ta.up(a[i].id,a[i].a),tb.up(a[i].id,a[i].b);
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(calc(mid)>calc(mid+1)) l=mid+1;
            else r=mid;
        }
        pre[i]=calc(l);
    }
    ta.clear(),tb.clear();
    double ans=INFINITY;
    for(int i=n;i>=1;i--){
        ta.up(a[i].id,a[i].a),tb.up(a[i].id,a[i].b);
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(calc(mid)>calc(mid+1)) l=mid+1;
            else r=mid;
        }
        ans=min(ans,pre[i-1]+calc(l));
    }
    write(ans);
    return 0;
}