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; }