P8365 [LNOI2022] 吃

如果确定了顺序，那么每个操作是独立的。对于一次操作如果需要选择加法需要满足：
$$
x + b > ax \Longrightarrow (a - 1)x < b
$$
当 $a = 1$ 时，显然成立。显然最后的结果一定是先选择若干个加法再若干个乘法，考察出现两次加法需要满足：

$$
\begin{cases}
(a _ 1 - 1) x < b _ 1 \\
(a _ 2 - 1)(x + b _ 1) < b _ 2 \\
(a _ 2 - 1) x < b _ 2 \\
(a _ 1 - 1)(x + b _ 1) < b _ 1
\end{cases}
$$

如果排除 $a _ 1$ 的部分，则有：

$$
\begin{cases}
0 < x < \frac {b _ 2} {a _ 2 - 1} - b _ 1 \\
0 < x < \frac {b _ 1} {a _ 1 - 1} - b _ 2
\end{cases}
$$

使得 $\frac {b _ 2} {a _ 2 - 1} + b _ 1$ 和 $\frac {b _ 1} {a _ 1 - 1} + b _ 2$ 最大，$a _ 1 = a _ 2 = 2$ ，$b _ 2 > b _ 1$ 和 $b _ 1 > b _ 2$ 矛盾，如果排除 $a _ 1$ 的部分，不存在两次加法。

考察选择哪一个数作为加法，$ans = (\prod a _ i ) \frac {x + b _ k} {a _ k}$ 。即选择最大的 $\frac {x + b _ k} {a _ k}$ 的 $k$ 。如果有 $(a _ k - 1)x > b _ k$ ，说明不选择加法最优。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 5e5 + 10, mod = 1e9 + 7;
int n, A[N], B[N];
int main ()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int i = 1; i <= n; ++i) read(B[i]);
    LL cur = 1;
    for (int i = 1; i <= n; ++i) if (A[i] == 1)
    {
        cur += B[i];
        swap(A[i], A[n]), swap(B[i], B[n]);
        --i, --n;
    }
    int t = -1;
    for (int i = 1; i <= n; ++i)
        if (!~t || ((cur + B[i]) * A[t] > (cur + B[t]) * A[i]))
            t = i;
    if ((LL)(A[t] - 1) * cur > B[t]) t = 0;
    else cur += B[t];
    for (int i = 1; i <= n; ++i) if (i ^ t)
        cur = cur * A[i] % mod;
    write(cur);
    return 0;
}