Description
Data Constraint
Solution
我们发现答案最多只有两条直线构成，自己简单画一下就成。 现在问题成了如何求两条直线构成的最优方案。 我们设两条向量分别为(a,b),(c,d)，价值分别为e,f，那么设(a,b)的时间为x，我们可以发现在
n−a∗xc<m−b∗xd
时,
f(x)=ex+f∗n−a∗xc=(e−a∗fc)x+n∗f/c
这就成了一次函数，求极值应该很容易。
Code
using namespace std;
const
int maxn=
1e3+
5;
const db mo=
1e-
10;
db
m[maxn],d[maxn],h[maxn],m1,m2,ans,
x,
y,z,l,r,mid,ans1[
3][
2];
int n,i,t,j,k,p;
db pan(db
x){
db
y=(m2-
x*m[i])/
m[j],z=(m1-
x*h[i])/h[j];
return x*d[i]+min(
y,z)
*d[j];
}
void make(db l){
if (pan(l)>ans){
ans=pan(l);ans1[
1][
0]=i,ans1[
1][
1]=l;
ans1[
2][
0]=j,ans1[
2][
1]=min((m2-l
*m[i])/
m[j],(m1-l
*h[i])/h[j]);
}
}
int main(){
freopen(
"terraria.in",
"r",stdin);freopen(
"terraria.out",
"w",stdout);
scanf(
"%d",&p);
while (p){
p--;scanf(
"%d%lf%lf",&n,&m1,&m2);
for (i=
1;i<=n;i++)scanf(
"%lf",&h[i]);
//m1
for (i=
1;i<=n;i++)scanf(
"%lf",&
m[i]);
//m2
for (i=
1;i<=n;i++)scanf(
"%lf",&d[i]);
ans=
0;memset(ans1,
0,sizeof(ans1));
for (i=
1;i<=n;i++){
x=min(m2/
m[i],m1/h[i]);
if (
x*d[i]>ans){
ans=
x*d[i];ans1[
1][
0]=i,ans1[
1][
1]=
x;
}
}
for (i=
1;i<=n;i++)
for (j=i+
1;j<=n;j++){
x=m2
*h[j]-m1
*m[j];
y=
m[i]
*h[j]-h[i]
*m[j];z=min(m2/
m[i],m1/h[i]);
if (
y>
0){
l=
x/
y;
r=min(m2/
m[i],m1/h[i]);
}
else{
l=
0;
r=
x/
y;
}
if (l<
0) l=
0;
if (r>z) r=z;
if (l<r){
if (d[i]-
m[i]
*d[j]/
m[j]>
0) make(r);
else make(l);
}
if (l) r=l,l=
0;
else l=r,r=min(m2/
m[i],m1/h[i]);
if (l<
0) l=
0;
if (r>z) r=z;
if (l<r){
if (d[i]-h[i]
*d[j]/
m[j]>
0) make(r);
else make(l);
}
}
printf(
"%.10lf\n",ans);
for (i=
1;i<=n;i++){
if (i!=ans1[
1][
0] && i!=ans1[
2][
0])
printf(
"0.0000000000 ");
else if (i==ans1[
1][
0])
printf(
"%.10lf ",ans1[
1][
1]);
else if (i==ans1[
2][
0])
printf(
"%.10lf ",ans1[
2][
1]);
}
printf(
"\n");
}
}
