[NOI2012]骑行川藏

[NOI2012]骑行川藏

思路一:二分导数

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
*/

 

思路二:拉格朗日乘数法

咕咕咕

上一篇:【NOI2012】迷失游乐园


下一篇:jQuery--checkbox全选/取消全选