[World Final 2017 E] Need For Speed (二分)

n<=1000的数据范围是一个坑,导致往O(n^2)算法方向想了很久.<还是我太弱辣>

正解:二分答案即可,O(nlogn)解决,大概是NOIP T1难度.提交网址:https://icpc.kattis.com/problems/speed

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
double d[1005],s[1005],t,minn=1e18;
int n,i;
int main (){
scanf ("%d%lf",&n,&t);
for (i=1;i<=n;i++)
{scanf ("%lf%lf",&d[i],&s[i]);
if (s[i]<minn) {minn=s[i];}
}
double l=-minn,r=1e18;
while (r-l>eps)
{double mid=(l+r)/2.00;
double tt=0;
for (i=1;i<=n;i++)
{tt+=d[i]/(s[i]+mid);}
if (tt>t) {l=mid;}
else {r=mid;}
}
printf ("%.10lf\n",l);
return 0;
}