a不等于1的食物中最多选择一个做加法。(不会证明,看的题解Q Q)
若都选择乘法,初始值为A时,易知这时体重为A*B,B为所有食物的a值乘积
选择一个做加法后,答案为(B+bi)/ai * A,可知选择最大的(B+bi)/ai即可为答案。
#include<cstdio>
#define ll long long
struct node
{
ll a,b;
};
ll n,ans=1;
node f[500010];
const ll mod=1000000007;
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&f[i].a);
}
for(ll i=1;i<=n;i++)
{
scanf("%lld",&f[i].b);
if(f[i].a==1)
{
ans=(ans+f[i].b)%mod;
}
}
ll flag=0;
f[0].a=1;//使第一次替换能成立
for(ll i=1;i<=n;i++)
{
if(f[i].a==1)
continue;
if((ans+f[i].b)*f[flag].a>(ans+f[flag].b)*f[i].a)//换位避免除法,以避免麻烦的精度问题
{
flag=i;
}
}
ans=(ans+f[flag].b)%mod;
for(ll i=1;i<=n;i++)
{
if(i==flag)
continue;
ans=(ans*f[i].a)%mod;
}
printf("%lld\n",ans);
return 0;
}