卧薪尝胆,厚积薄发。
HNOI2011 赛车游戏
Description:
给出
$a,b,d_i,s_i$
,要求:
$$
\sum_{i=1}^nd_i(\max(0,ax_i+bs_i))\leqslant E
$$
最大化:
$$
f(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{d_i}{x_i}
$$
要求
$v\leqslant maxv$
$1\leqslant t\leqslant 100,1\leqslant n\leqslant 10^4$
Solution:
首先
$ax_i+bs_i\geqslant 0$
一定比
$<0$
更优,所以那个大于号其实没用,根据骑行川藏的经验我们可以套用拉格朗日乘数法:
$$
L(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{d_i}{x_i}+\lambda(\sum_{i=1}^n(d_iax_i+d_ibs_i)-E)
$$
求偏导得:
$$
L'(x_i)=-d_ix_i^{-2}+\lambda d_ia=0\\
\lambda ax_i^2=1
$$
我们发现所有的
$x_i$
都应该是一样的。
于是二分
$x_i$
,然后判断
$\varphi$
的值即可。
Code:
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
double a,b,vmax,E;
int n;
#define MAXN 10010
double d[MAXN],s[MAXN];
double calc(double v)
{
double sum = 0;
for(int i = 1;i <= n;++i)
{
sum += max(0.0,d[i] * (a * v + b * s[i]));
}
return sum;
}
#define eps 1e-12
void work()
{
scanf("%lf%lf%lf%lf",&a,&b,&vmax,&E);
scanf("%d",&n);
double x,y;
for(int i = 1;i <= n;++i)
{
scanf("%lf%lf",&x,&y);
x /= 1000;y /= 1000;
d[i] = sqrt(x * x + y * y);
s[i] = y / x;
}
double l = 0,r = vmax,mid;
for(int i = 1;i <= 50;++i)
{
mid = (l + r) / 2;
if(calc(mid) <= E)l = mid;
else r = mid;
}
double ans = 0.0;
for(int i = 1;i <= n;++i)
{
double o = a * l + b * s[i];
double v = l;
if(o <= eps)
{
v = min(-b * s[i] / a,vmax);
}
if(v <= eps)
{
puts("IMPOSSIBLE");
return;
}
ans += d[i] / v;
}
printf("%.5lf\n",ans);
return;
}
int main()
{
int testcases;
scanf("%d",&testcases);
while(testcases--)work();
return 0;
}

Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡