CodeForces - 813C The Tag Game(拉格朗日乘数法,限制条件求最值)
2024-09-28 01:29:53
【传送门】http://codeforces.com/problemset/problem/813/C
【题意】给定整数a,b,c,s,求使得 xa yb zc值最大的实数 x,y,z , 其中x + y + z <= s. (1 ≤ S ≤ 103 , 0 ≤ a, b, c ≤ 103)
【题解】设P(x,y,z ) = xa yb zc,则P(x,y,z)是递增的,要使 函数值尽可能地大,那么必取 x + y + z = s
问题转化成:已知限定条件 x + y + z = s, 求P(x,y,z)取得最大值的(x,y,z)
显然,这是运用拉格朗日乘数法的模板题。
【拉格朗日乘数法】
解决的问题模型 : 已知G(x,y,z) = 0
求F(x,y,z)最值(或者极值,一般情况下拉格朗日乘数法求得的极值点就是最值点)
设L(x,y,z) = F(x,y,z) + λG(x,y,z)
将L(x,y,z)分别对x,y,z求偏导,得到3个四元一次方程,加上原来的一个限定条件G(x,y,z) = 0,共得到4个方程,解4个未知数(x,y,z,λ)
求出极值点(x, y , z)即可。
最值只可能在边界处或者极值点处取到,一般情况下极值点就是最值点。
【回到本题】令G(x,y,z) = x + y + z - s , F(x,y,z) = alnx + blny + clnz .用上述方法解出极值点(s*a/(a+b+c) , s*b/(a+b+c), s*c/(a+b+c))这就是所求答案。
注意a + b + c = 0的特判情况,还需要注意精度,题目要求1e-6,但是精度要达到1e-10以上才行,不然会WA,有点坑。
【AC代码】
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iomanip>
using namespace std;
typedef long long ll; double s;
double a,b,c; int main(){
while(cin>>s){
cin>>a>>b>>c;
if(a + b + c == ){
cout<<1.0*s<<" "<<<<" "<<<<endl;
continue;
}
cout<<setiosflags(ios::fixed)<<setprecision()<<s/(a+b+c)*a<<" "<<s/(a+b+c)*b<<" "<<s/(a+b+c)*c<<endl;
}
}
最新文章
- DataView详解
- MVC自定义分页(附表跳转页Loading提示)
- 读取Properties键值对
- 开始使用 Fresco
- Cpp多重继承会产生的问题
- windows防火墙无法启动,服务不存在
- Linux下通过shell脚本创建账户
- Stones
- bzoj3514
- apache开源项目--nutch
- IntelliJ Idea 常用快捷键列表(精简版)
- hql语句拼接的替换方式
- Mac电脑使用Android Studio进行真机调试
- Mysql 的 IF 判断
- HTTP 首部字段详细介绍
- Django—templates系统:模版语言
- glusterfs4.0.1 mempool 分析笔记
- 【Spark篇】---Spark中Action算子
- 实现鼠标悬停,div勾画div边框的动画
- Building tools 为什么是主流?
热门文章
- 【倍增】7.11fusion
- (30)zabbix Trapper 监控项配置
- FTP实验报告
- 微信开发 access_token 数量限制问题
- 关于Linux上的SSH服务无法启动,提示“/var/empty/sshd must be owned by root and not group or world-writable”错误
- 暴力解说之首次部署NGINX
- 关于priority_queue的一些说明
- ZOJ 2058 The Archaeologist&#39;s Trouble II(贪心+模拟)
- python中map()函数的用法讲解
- Knockout v3.4.0 中文版教程-11-控制文本内容和外观-text绑定