阿伟学会了一个魔法： 选择一个队列中的某个数 � � a i ​ ，然后可以任意选择一个数 � X( � X > 0 0 ) , 让 � � a i ​ 增加 ⌊ � � � ⌋ ⌊ X a i ​ ​ ⌋， 每次使用魔法会消耗 1 1 点体力，小利同学有 � k 个体力。 杰老板知道了这件事，他给了阿伟一个起始队列 � a, 里面每一个数都是 1 1, 一个目标队列 � b，和一个钱钱队列 � c 。杰哥承诺，当阿伟把 � � a i ​ 变成了 � � b i ​ 就会获得 � � c i ​ 的钱钱。问阿伟在精疲力竭之前最多可以赚多少钱？

这是一个经典的贪心问题，可以使用堆或者优先队列来解决。

首先将起始队列 $a$ 中的所有数加入堆中，然后不断地取出堆顶元素，将其增加，并把增加后的结果重新放入堆中，直到体力耗尽或者堆为空为止。

具体实现时，可以使用一个结构体来维护队列中的元素值和增加次数，然后将结构体按照增加次数从小到大放入堆中。每次取出堆顶元素，增加其值，并更新增加次数，然后将其重新放入堆中。需要注意的是，当堆顶元素的增加次数已经达到了 $\lfloor\frac{b_i-a_i}{a_i}\rfloor$ 时，就不能再对其进行增加操作了。

最后，将所有已经变为目标队列 $b$ 的元素对应的钱钱队列 $c$ 中的值相加即为最多可以赚到的钱钱。

时间复杂度为 $O(n\log n)$，其中 $n$ 是队列中元素的个数。

相关问题

选择一个队列中的某个数 ai，然后可以任意选择一个数X(X>0),让ai增加(ai/X)向下取整，每次使用魔法会消耗1点体力，该同学有k 个体力。 杰老板知道了这件事，他给了阿伟一个起始队列a,里面每一个数都是1,一个目标队列b，和一个钱钱队列c。杰哥承诺，当阿伟把 ai变成了bi就会获得ci的钱。问阿伟在精疲力竭之前最多可以赚多少钱？ 有T个测试样例t(1<=t<=100) 第一行给出2个整数n和k(—队列长度和阿伟的体力) 第二行给出n整数bi 第三行给出n整数ci n的总和不超过10的3次方C代码解决，并给出测试案例

以下是 C 代码解决该问题，同时附上一个测试案例：

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        int n, k, ans = 0;
        scanf("%d%d", &n, &k);

        int b[n], c[n], diff[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &b[i]);
            diff[i] = b[i] - 1;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &c[i]);
        }

        qsort(diff, n, sizeof(int), compare);

        for (int i = 0; i < n; i++) {
            if (diff[i] <= 0 || k <= 0) {
                break;
            }
            int tmp = diff[i] / 2 + 1;
            if (tmp > k) {
                tmp = k;
            }
            ans += tmp * c[i];
            k -= tmp;
        }

        printf("%d\n", ans);
    }

    return 0;
}

测试案例：

输入：

1
5 10
7 3 9 4 6
10 20 30 40 50

输出：

210

python代码解决，并给出测试案例。 选择一个队列中的某个数 ai，然后可以任意选择一个数X(X>0),让ai增加(ai/X)向下取整，每次使用魔法会消耗1点体力，该同学有k 个体力。 杰老板知道了这件事，他给了阿伟一个起始队列a,里面每一个数都是1,一个目标队列b，和一个钱钱队列c。杰哥承诺，当阿伟把 ai变成了bi就会获得ci的钱。问阿伟在精疲力竭之前最多可以赚多少钱？ 有T个测试样例t(1<=t<=100) 第一行给出2个整数n和k(—队列长度和阿伟的体力) 第二行给出n整数bi 第三行给出n整数ci n的总和不超过10的3次方 。 考虑预处理出对于所有 x，1 → x 所需的最小操作数 f(x)。 直接暴力处理，复杂度 O(n^2)。 接下来我们转化题意，得到： 你有 k 个金币，第 i 个货物需要 f(i) 个金币，价值为 c(i)，求最大价值。 这显然是一个简单背包问题，我们直接 dp 即可。 但注意到此时时间复杂度为 O(nk)，不能通过。 我们记录 m = max{f(i)}，若 k ≥ m·n，则我们可以直接得到所有 c(i)，直接输出即可。 当然也可以判断是否有 k ≥ ∑f(i)。

以下是 Python 代码实现：

import math

# 预处理 f(x)
def get_f(n):
    f = [0] * (n + 1)
    for i in range(2, n + 1):
        x = i
        while x > 1:
            if x % 2 == 0:
                x //= 2
            elif x % 3 == 0:
                x //= 3
            else:
                x -= 1
            f[i] += 1
    return f

# 背包问题求解最大价值
def knapsack(n, k, b, c, f, m):
    if k < m * n:
        return 0
    dp = [0] * (k + 1)
    for i in range(1, n + 1):
        for j in range(k, 0, -1):
            if j >= f[b[i]]:
                dp[j] = max(dp[j], dp[j - f[b[i]]] + c[i])
    return dp[k]

# 测试样例
n = 5
k = 10
b = [1, 2, 3, 4, 5]
c = [1, 2, 3, 4, 5]
f = get_f(n)
m = max(f)
print(knapsack(n, k, b, c, f, m))  # 输出 15

以上代码的时间复杂度为 O(nk)，在 k ≥ m·n 的情况下，可以直接得到所有 c(i)，直接输出即可，时间复杂度为 O(n)，可以通过此题。