P8365 [LNOI2022] 吃题解 题解

· · 题解

解题思路：

首先对于任意 a_i 等于 1 的食物，一定会选择加上 b_i，这是显然的。

然后可以发现一个性质，就是最多只会有一个食物被用于加上 b_i，其他的一定会用来乘上 a_i。原因是在考虑两个食物 a_1,b_1 和 a_2,b_2，全都用于增加获得的价值为 b_1+b_2，而将其中的某一个换成乘，由于在经过第一步处理之后有 a_i\ge 2，所以 \max(b_1a_2,b_2a_1)\ge b_1+b_2，当然也不排除 a_1a_2\ge b_1+b_2。

由此其实也就得出了贪心的策略，一开始先选择所有的 a_i=1 的吃下去，此时的体重为 k，然后依次考虑每一个剩下的食物，和当前的选择 a_x,b_x 进行比较，也就是 (k+b_x)\times a_i 和 (k+a_i)\times b_x 进行比较。特殊地，令不选择为 b_x=0 且 a_x=1。

注意随时取模和使用长整型变量。

代码：

#include<cstdio>
using namespace std;
#define int long long
const int MAXN=500005,MOD=1e9+7;
int n,a[MAXN],b[MAXN],k,ans;
signed main(){
    scanf("%d\n",&n);
    a[0]=1;k=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)if(a[i]==1)k=(k+b[i])%MOD;
    for(int i=1;i<=n;i++){
        if(a[i]==1)continue;
        if((k+b[ans])*a[i]<(k+b[i])*a[ans])
        ans=i;
    }
    k=(k+b[ans])%MOD;
    for(int i=1;i<=n;i++){
        if(i==ans)continue;
        k=(k*a[i])%MOD;
    }
    printf("%lld\n",k);
    return 0;
}