Codeforces

Luogu

分析

首先考虑怎么放最优。考虑邻项交换法
$$
a_i\left(1-\frac{c(t+t_i)}{T}\right)+a_j\left(1-\frac{c(t+t_i+t_j)}{T}\right)>a_j\left(1-\frac{c(t+t_j)}{T}\right)+a_i\left(1-\frac{c(t+t_i+t_j)}{T}\right)
$$
化简得到
$$
a_it_j>a_jt_i
$$
于是按照 $\frac{a_i}{t_i}$ 从大到小排序即可。

一个想法是二分答案，check 时按 $a_i$ 排序然后看 $a_i\left(1-\frac{cx}{T}\right)$ 是否满足条件。但很容易发现这个是假的，因为 $\frac{a_i}{t_i}$ 相同的题目无法确定顺序，从而无法确定完成时间。于是我们记一下可能的完成时间的最大值和最小值，并在 check 时拿 $a_i\left(1-\frac{cx}{T}\right)$ 的最小值去和前面的最大值比较即可。

代码

//  ====================================
//    author: M_sea
//    website: https://m-sea-blog.com/
//  ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=150000+10;

int n;
struct pro { int a,t; ll mx,mn; } a[N];
ll s[N],T;

bool check(double c) {
    double mx=0,tmx=0;
    for (int i=1;i<=n;++i) {
        if (a[i].a!=a[i-1].a) mx=tmx;
        if (a[i].a*(1-c*a[i].mx/T)+1e-8<mx) return 0;
        tmx=max(tmx,a[i].a*(1-c*a[i].mn/T));
    }
    return 1;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i].a=read();
    for (int i=1;i<=n;++i) a[i].t=read(),T+=a[i].t;
    sort(a+1,a+n+1,[](pro a,pro b) { return 1ll*a.a*b.t>1ll*b.a*a.t; });
    for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i].t;
    for (int i=1,j;i<=n;i=j+1) {
        j=i;
        while (j<n&&1ll*a[i].a*a[j+1].t==1ll*a[j+1].a*a[i].t) ++j;
        for (int k=i;k<=j;++k) a[k].mn=s[i-1]+a[k].t,a[k].mx=s[j];
    }
    sort(a+1,a+n+1,[](pro a,pro b) { return a.a<b.a; });
    double L=0,R=1;
    while (R-L>1e-7) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    printf("%.7lf\n",L);
    return 0;
}