思路一：二分导数
http://www.cnblogs.com/RabbitHu/p/9019762.html
考虑“性价比”即花费单位能量缩短的时间。
如果我们给每一段随机分配一个速度，再调整
那么一定选择性价比最高的调整，或者把性价比较低的能量取回，再分配
而性价比随着能量分配，会越来越低
可以发现的是，最后所有的n段的性价比一定都相同！
（如果存在不同的，那么一定可以从性价比较低的收回一些能量，给性价比高的用，使得总时间更少）
由于实数范围，所以暴力模拟用个堆什么的不现实
考虑用数学方法：
每段的t-E图像是一个类反比函数
每个点的斜率就是当前能量的性价比！
就是$e_i$位置的导数
也即，最后的所有图像$e_i$的导数都是一样的！（并且都是负数）
而且可以发现，最后导数负数绝对值越小（导数越大），那么花费的总能量越多，时间越短
所以有二分的性质！
二分导数，考虑怎么检验
直观的想法是求出t-E的导数关于E的函数，，，没法求
但是，t和v的图像的导数就是y=si/x的导数可以求，E和v的导数根据关系式可以直接求
所以考虑通过v作为中介，求出t-E的导数关于v的函数
（看上面博客）然后就得到了式子，对于二分的导数，解方程求出$v_i$，再求出$e_i$，通过e的总和判断二分走向
至于解方程，就用二分即可。（由于等式一边是正数，所以一定有$v_i>v_i'$）
一些精度问题：（本题精度要求还是比较高的）
1.二分解方程判断的时候，能不用除法就不要用除法！但是不等式记得变号！（因为x小于零）
2.eps 1e-14（也可以不用eps，二分100次左右就结束（看人品。。。））
代码：
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=1e4+4; const double eps=1e-14; double ans; double s[N],vi[N],k[N]; int n; double eu; double jie(double x,int i){ double l=max(vi[i],(double)0),r=100000.0; double ret=0.00; int cnt=60; while(r-l>eps){ double mid=(l+r)/2; if(mid*mid*(mid-vi[i])*2*k[i]*x<=-1) r=mid; else l=mid; } ret=(l+r)/2; return ret; } double che(double mid){ double sum=0; for(reg i=1;i<=n;++i){ double v=jie(mid,i); sum+=k[i]*s[i]*(v-vi[i])*(v-vi[i]); } return sum; } int main(){ rd(n); scanf("%lf",&eu); for(reg i=1;i<=n;++i){ scanf("%lf%lf%lf",&s[i],&k[i],&vi[i]); } double r=0.0,l=-100000000.00; int cnt=100; while(r-l>eps){ double mid=(l+r)/2.0; double now=che(mid); if(now<=eu) l=mid; else r=mid; } double mid=(l+r)/2.0; for(reg i=1;i<=n;++i){ ans+=s[i]/jie(mid,i); } printf("%.10lf",ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/5 11:36:13 */
思路二：拉格朗日乘数法
咕咕咕