「LNOI2022」吃

#题面

#题目描述

小 A 很喜欢吃东西。

小 A 面前有 $n$ 份食物，第 $i$ 份有参数 $a_i$ 和 $b_i$。小 A 可以按照任意顺序吃掉这 $n$ 份食物。当她吃掉编号为 $i$ 的食物时，她可以选择将自己的体重乘以 $a_i$ 或者将自己的体重加上 $b_i$。每份食物只能吃恰好一次。

小 A 的初始体重为 $1$，请求出她吃完 $n$ 份食物后能达到的最大体重。答案可能很大，你只需要输出其对 $({10}^9 + 7)$ 取模后的结果。

注意：你需要最大化体重并将该最大值对 $\bm{({10}^9 + 7)}$ 取模，而非最大化体重对 $\bm{({10}^9 + 7)}$ 取模的结果。

#输入格式

第一行输入一个整数 $n$ 表示食物的数量。第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示每份食物的参数。

#输出格式

输出一个整数，表示小 A 可以得到的最大体重对 $(10^9 + 7)$ 取模后的结果。

#输入输出样例

样例输入 #1

5
1 2 3 4 5
100 200 300 400 500

样例输出 #1

18060

样例解释 #1

以下方案可以达到最大体重：

• 吃掉第一份食物并选择将体重增加 $100$，体重变为 $101$；
• 吃掉第二份食物并选择将体重增加 $200$，体重变为 $301$；
• 吃掉第三份食物并选择将体重乘 $3$，体重变为 $903$；
• 吃掉第四份食物并选择将体重乘 $4$，体重变为 $3612$；
• 吃掉第五份食物并选择将体重乘 $5$，体重变为 $18060$。

样例 #2

见附加样例中的 sample/food2.in 与 sample/food2.ans。

该组样例满足 $n \le 10$ 和特殊性质 E。

样例 #3

见附加样例中的 sample/food3.in 与 sample/food3.ans。

该组样例满足 $n \le 20$ 和特殊性质 E。

样例 #4

见附加样例中的 sample/food4.in 与 sample/food4.ans。

该组样例满足 $n \le 2000$。

样例 #5

见附加样例中的 sample/food5.in 与 sample/food5.ans。

该组样例满足特殊性质 A。

样例 #6

见附加样例中的 sample/food6.in 与 sample/food6.ans。

该组样例满足特殊性质 C。

样例 #7

见附加样例中的 sample/food7.in 与 sample/food7.ans。

该组样例满足特殊性质 D。

样例 #8

见附加样例中的 sample/food8.in 与 sample/food8.ans。

该组样例满足特殊性质 B。

样例 #9

见附加样例中的 sample/food9.in 与 sample/food9.ans。

#数据范围与约定

对于 $100 \%$ 的测试数据，$1 \le n \le 5 \times {10}^5$，$1 \le a_i, b_i \le {10}^6$。

• 特殊性质 A：$a_i = 1$；
• 特殊性质 B：$a_i \ge b_i$；
• 特殊性质 C：$a_i, b_i$ 在 $[1, 10^6]$ 内独立均匀随机生成；
• 特殊性质 D：$a_i \ge 2$；
• 特殊性质 E：$a_i \le 4$。

#思路

容易发现当 $a_i = 1$ 时，选择将体重加上 $b_i$ 显然是更优的，那么可以先处理一遍这种情况，并更新答案，记为 $B$。

然后剩下的食物都满足 $a_i \geq 2$，此时最多进行一次 $+ b_i$ 操作（令 $b_1 \geq b_2$，显然 $b_1 \times a_2 \geq b_1 + b_2$），设 $A = \prod_{i \in S} a_i$（$S$ 为剩余食物的集合），分类讨论如下：

1. 当不进行 $+ b_i$ 操作时，答案为 $A \times B$。
2. 当仅进行 $1$ 次 $+ b_i$ 操作时，答案为 $\displaystyle A \times \max_{i \in S} \{\frac{B + b_i}{a_i}\}$。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const int mod = 1e9 + 7;

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

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            ans = (static_cast<long long>(ans) + b[i]) % mod;
            a[i] = -1;
        }
    }

    long double max = ans;
    int max_id = -1;

    for (int i = 1; i <= n; i++) {
        if (~a[i]) {
            long double t = static_cast<long double>(static_cast<long long>(ans) + b[i]) / a[i];

            if (t > max) {
                max = t;
                max_id = i;
            }
        }
    }

    if (~max_id) {
        a[max_id] = -1;
        ans = (static_cast<long long>(ans) + b[max_id]) % mod;
    }

    for (int i = 1; i <= n; i++) {
        if (~a[i]) {
            ans = static_cast<long long>(ans) * a[i] % mod;
        }
    }

    cout << ans << endl;

    return 0;
}