警示前人(#19)& 吐槽
查看原帖
警示前人(#19)& 吐槽
414231
_Fatalis_楼主2022/3/15 13:09

蒟蒻の吐槽:蓝题?不至于吧


若 WA 了 #19,那么说明你的程序有可能上界没开够!

/*
bi/ai=k
p/ai=P  (s/s)
*/
#include<bits/stdc++.h>
using namespace std;
int n;
double k[100001],P[100001];

bool check(double t)
{
    double sum=0;
    for(int i=1;i<=n;i++)
        if(k[i]<t)
            sum+=(t-k[i])/P[i];
    
    return sum<=t;
}

bool cp(double a,double b)
{
    return a*100000+1<b*100000;   //精度再高就爆 TLE
}

int main()
{
    int p,a,b;
    double l=1e8,r=1.5e10;  //要开到 1e10 以上
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>a>>b,k[i]=1.0*b/a,P[i]=1.0*p/a,l=min(k[i],l);
    while(cp(l,r))
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    if(l>=1e10) cout<<-1<<endl;
    else cout<<l<<endl;
    return 0;
}
2022/3/15 13:09
加载中...