题解：CF2193D Monster Game#

思路#

使用贪心方法。

首先要把剑的威力 $a_i$ 降序排序，在 $x$ 最大的情况下通过关卡，之后我们遍历每个 $b_i$ ，在使 $x$ 尽量大的情况下枚举每一个关卡，最后输出得分的最大值 $max(ans, a_{sum} * i)$ 。

复杂度#

时间复杂度： $O(n\times{}log n)$
空间复杂度： $O(n)$

代码#

1
#include <bits/stdc++.h>
2
#define int long long //不开long long会WA
3
#define inc(i, l, r) for (int i = l; i <= r; i++)
4
#define dec(i, r, l) for (int i = r; i >= l; i--)
5
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
6
using namespace std;
7
/*===================祖传头模板=====================*/
8
const int N = 2e5 + 5; // 1 <= n <= 2e5
9
int a[N], b[N];
10
signed main()
11
{
12
    int t, n;
13
    cin >> t;
14
    while (t--)
15
    {
16
        cin >> n;
17
        inc(i, 1, n)
18
        {
19
            cin >> a[i];
20
        }
21
        inc(i, 1, n)
22
        {
23
            cin >> b[i];
24
        }
25
        sort(a + 1, a + n + 1, [](int x, int y){return x > y;}); // 降序排序
26
        int ans = INT_MIN, sum = 0;
27
        inc(i, 1, n) // 枚举b[i]
28
        {
29
            if (sum + b[i] > n)
30
                break; // 剑不够了就放弃
31
            sum += b[i]; // 累加通过第i关的剑的威力
32
            ans = max(ans, a[sum] * i); // 取最大得分
33
        }
34
        cout << ans << endl; // 输出答案
35
    }
36
    return 0;
37
}