Luogu8365

Luogu8365 [LNOI2022]吃

Description

有 个物品，每个物品有两个属性 与 。

你有一个属性 ，对于每个物品，你可以选择让 或 。

你可以任意重排物品的顺序。求 的最大值。

最终答案对 取模。

。

Sol

时选择加更优，先加上。

然后这里有一个结论：加都在乘前面进行，最多加一次。

证明：设加了 ，则 ，选择乘法更优。

设加的是 ，从乘改到加的新答案是 ，取最大值即可。

时间复杂度线性。

Code

//这份代码的完成时间比较久远，所以相较现在的马蜂有些差别，不影响食用XD
#include<bits/stdc++.h>
#include<cstdio>
const int M=5e5+5;
const int Mod=1e9+7;
#define int long long
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

int n,a[M],b[M],ans=1;

signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=read();
    for(int i=1;i<=n;)if(a[i]==1){
        ans+=b[i];
        std::swap(a[i],a[n]);
        std::swap(b[i],b[n]);
        n--;
    }else i++;
    int p=0;
    long double maxn=ans;
    for(int i=1;i<=n;++i){
        long double x=(ans+b[i]*1.0)/a[i];
        if(x>maxn)p=i,maxn=x;
    }
    ans%=Mod;
    if(p)(ans+=b[p])%=Mod;
    for(int i=1;i<=n;++i)if(p!=i)(ans*=a[i])%=Mod;
    printf("%lld\n",ans);
    return 0;
}