bzoj2876 [NOI2012]骑行川藏(拉格朗日乘数法)

时间:2022-09-22 14:02:35

题目描述

蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。

由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响)。某一天他打算骑\(N\)段路,每一段内的路况可视为相同:对于第\(i\)段路,我们给出有关这段路况的3个参数 \(s_i ,k_i ,v_i'\) ,其中 \(s_i\) 表示这段路的长度, \(k_i\) 表示这段路的风阻系数, \(v_i'\) 表示这段路上的风速(表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响)。若某一时刻在这段路上骑车速度为\(v\),则他受到的风阻大小为 \(F = k_i ( v - v_i' )^2\)(这样若在长度为\(s\)的路程内保持骑行速度\(v\)不变,则他消耗能量(做功)\(E = k_i ( v - vi' )^2 s\)。

设蛋蛋在这天开始时的体能值是 \(Eu\) ,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间\(T\)是多少。

输入输出格式

输入格式:

第一行包含一个正整数\(N\)和一个实数\(Eu\),分别表示路段的数量以及蛋蛋的体能值。

接下来\(N\)行分别描述\(N\)个路段,每行有3个实数 \(s_i , k_i , v_i'\) ,分别表示第 \(i\) 段路的长度,风阻系数以及风速。

输出格式:

输出一个实数\(T\),表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后\(6\)位。

输入输出样例

输入样例#1:

3 10000
10000 10 5
20000 15 8
50000 5 6

输出样例#1:

12531.34496464

说明

【数据规模与约定】

对于10%的数据,\(N=1\);

对于40%的数据,\(N<=2\);

对于60%的数据,\(N<=100\);

对于80%的数据,\(N<=1000\);

对于所有数据,\(N \leq10000\),\(0 \leq Eu \leq 10^8,0 < s_i \leq 100000,0 < k_i \leq 1,-100 < v_i' < 100\)。数据保证最终的答案不会超过\(10^5\)。

【提示】

必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式。

题解

先讲一讲拉格朗日乘数法:

拉格朗日乘数法是用来解决多元函数的最优值问题(最大、最小)

一般形式为:函数\(f(x_1,x_2,x_3..x_n)\)满足限制\(g_i(x_1,x_2,x_3...x_n)=0,(i\in 1,2,3....m)\)

解法:定义\(h(x_1,x_2,x_3...x_n,\lambda_1,\lambda_2,\lambda_3...\lambda_m)=f(x_1,x_2,x_3...x_n)+\Sigma_{i=1}^m\lambda_ig_i(x_1,x_2,x_3...x_n)\)

函数\(h\)的极值就是函数\(f\)的最优值

\(h\)极值用导数求

再回到这道题,只需要满足一种限制:\(g(x)=\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')^2\leq Eu\),并且,当\(g(x)=Eu\)时最优;

于是就有\(g(x)\)函数:\(g(x)=\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')^2-Eu=0\)

\(f(x)\)函数为:\(f(x)=\Sigma_{i=1}^n \frac {s_i}{x_i}\),\(x_i\)为每段路的骑行速度

则\(h(x)=\Sigma_{i=1}^n \frac{s_i}{x_i}+\lambda\ast\Sigma s_i\ast k_i(x_i-v_i')^2-Eu\)

将它求导:\(h'(x)=-\Sigma_{i=1}^n \frac{s_i}{x_i^2}+2\ast\lambda\ast\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')\)

二分求\(h'(x)=0\)时的\(x\)值

二分时每一个\(x_i\)也是二分求

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<vector>
#include<cstdlib>
#define QAQ int
#define TAT long long
#define OwO bool
#define ORZ double
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))
using namespace std;
const QAQ N=10005;
QAQ n;
ORZ m;
struct data{
ORZ s,k,v;
}a[N];
ORZ l,r,ans,v[N];
OwO pd(ORZ lmd){
F(i,1,n){
ORZ l=a[i].v,r=1000000,ans=0;
F(j,1,100){
ORZ mid=(l+r)/2.0;
if(2*lmd*a[i].k*mid*mid*(mid-a[i].v)<=1.0) l=mid,ans=mid;
else r=mid;
}
v[i]=ans;
}
ORZ ans=0;
F(i,1,n) ans+=a[i].k*(v[i]-a[i].v)*(v[i]-a[i].v)*a[i].s;
return ans>=m;
}
QAQ main(){
scanf("%d%lf",&n,&m);
F(i,1,n) scanf("%lf%lf%lf",&a[i].s,&a[i].k,&a[i].v);
l=0;r=10000000;
F(i,1,100){
ORZ mid=(l+r)/2.0;
if(pd(mid)) l=mid;
else r=mid;
}
F(i,1,n) ans+=a[i].s/v[i];
printf("%.6lf\n",ans);
return 0;
}

bzoj2876 [NOI2012]骑行川藏(拉格朗日乘数法)的更多相关文章

  1. &lbrack;BZOJ2876&rsqb;&lbrack;NOI2012&rsqb;骑行川藏&lpar;拉格朗日乘数法)

    题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2876 分析:就是要求约束条件下函数的极值,于是拉格朗日乘数列方程,发现化简后的关于vi ...

  2. bzoj 2876&colon; &lbrack;Noi2012&rsqb;骑行川藏 拉格朗日数乘

    2876: [Noi2012]骑行川藏 Time Limit: 20 Sec  Memory Limit: 128 MBSec  Special JudgeSubmit: 1033  Solved: ...

  3. BZOJ2876 &lbrack;Noi2012&rsqb;骑行川藏 【拉格朗日乘数法】

    题目链接 BZOJ 题解 拉格朗日乘数法 拉格朗日乘数法用以求多元函数在约束下的极值 我们设多元函数\(f(x_1,x_2,x_3,\dots,x_n)\) 以及限制\(g(x_1,x_2,x_3,\ ...

  4. bzoj2876 &lbrack;Noi2012&rsqb;骑行川藏

    Description 蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨.川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因 ...

  5. &lbrack;NOI2012&rsqb;骑行川藏——拉格朗日乘子法

    原题链接 不会啊,只好现学了拉格朗日乘子法,简单记录一下 前置芝士:拉格朗日乘子法 要求\(n\)元目标函数\(f(x_1,x_2,...,x_n)\)的极值,且有\(m\)个约束函数形如\(h_i( ...

  6. bzoj 2876&colon; &lbrack;Noi2012&rsqb;骑行川藏【拉格朗日乘数法&plus;二分】

    详见: http://blog.csdn.net/popoqqq/article/details/42366599 http://blog.csdn.net/whzzt/article/details ...

  7. 题解 洛谷 P2179 【&lbrack;NOI2012&rsqb;骑行川藏】

    题意为在满足\(\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i\leqslant E_U\)的条件下最小化\(\sum\limits_{i=1}^n\frac{ ...

  8. 2876&colon; &lbrack;Noi2012&rsqb;骑行川藏 - BZOJ

    Description 蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨.川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因 ...

  9. 【BZOJ】2876&colon; &lbrack;Noi2012&rsqb;骑行川藏

    题意 给出\(s_i, k_i, v_i', E\),满足\(\sum_{i=1}^{n} k_i s_i ( v_i - v_i' )^2 \le E, v_i > v_i'\),最小化$ \ ...

随机推荐

  1. 常用正则表达式大全!(例如:匹配中文、匹配html)

    一.常见正则表达式 匹配中文字符的正则表达式: [u4e00-u9fa5]    评注:匹配中文还真是个头疼的事,有了这个表达式就好办了  匹配双字节字符(包括汉字在内):[^x00-xff]  评注 ...

  2. 【hibernate 执行方法未插入数据库】hibernate的save方法成功执行,但是未插入到数据库

    今天做项目,碰上这个问题: hibernate的save方法成功执行,但是未插入到数据库. Dao层代码: @Override public void save(T t) { this.getSess ...

  3. 实现CCLayer只显示一个矩形可见区域

    转自:http://blog.csdn.net/while0/article/details/11004147 CCLayer的区域可能会比较大,怎样让它只显示其中一部分区域呢?  这个还是有很多场景 ...

  4. 1&colon;环境安装与介绍:canopy

    <利用python进行数据分析>这本书推荐用的的环境为EPDFree版本,但实际现在大概已经抛弃它改用Canopy了,下面将介绍Canopy相关: 一:下载:https://store.e ...

  5. android 向SD卡写入数据

    原文:android 向SD卡写入数据 1.代码: /** * 向sdcard中写入文件 * @param filename 文件名 * @param content 文件内容 */ public v ...

  6. JS可维护性代码

    最近在看一本Js的书名叫“Javascript高级程序设计”在里面学到了很多东西,是一本不错的书,非常值得一看. 解耦css/javascript element.style.color=" ...

  7. php中const与define的区别

    1 版本差异: const 要求php的版本>5.3.0 define 可以兼容php4,php5 等版本 2 定义的位置区别: const关键字定义的常量是在编译时定义的,因此const关键字 ...

  8. 为了解决linux配置Nginx 只能关闭防火墙才能访问的问题

    使用Nginx和iptables做访问权限控制(IP和MAC)     之前配置的服务器,相当于对整个内网都是公开的,而且,除了可以通过80端口的nginx来间接访问各项服务,也可以绕过nginx,直 ...

  9. C&num;——Nhibernate探索

    C#—Nhibernate探索 本篇文章,让我们一起来探索Nhibernate. 首先我们去搜索Nhibernate下载地址,如下链接所示. 该版本可能是最新版,我下载的4.0.4.GA.其中GA意思 ...

  10. IIS部署ASP&period;Net Core 502&period;5错误和解决

    在Win7的机器上部署ASP.Net Core程序,老是提示502.5错误. 已经安装了 Microsoft Visual C++ 2015 Redistributable .NET Core Win ...