跳转至

2838. 英雄可以获得的最大金币数 🔒

题目描述

在一场战斗中，n 位英雄正在试图击败 m 个怪物。你将得到两个下标从 1 开始的 正整数 数组 heroes 和 monsters，长度分别为 n 和 m。数组 heroes[i] 代表第 i 位英雄的力量，而 monsters[i] 代表第 i 个怪物的力量。

如果 monsters[j] <= heroes[i]，则第 i 位英雄可以击败第 j 个怪物。

你还将获得一个下标从 1 开始的 正整数 数组 coins，长度为 m 。数组 coins[i] 表示每位英雄在击败第 i 个怪物后可以获得的金币数。

返回一个长度为 n 的数组 ans，其中 ans[i] 是第 i 位英雄从这场战斗中能收集到的 最大 金币数。

注意

  • 击败怪物后，英雄的生命值不会减少。
  • 多位英雄可以击败同一个怪物，但每个怪物只能被同一位英雄击败一次。

 

示例 1：

输入：heroes = [1,4,2], monsters = [1,1,5,2,3], coins = [2,3,4,5,6]
输出：[5,16,10]
解释：对于每位英雄，我们列出了所有他可以击败的怪物的下标：
第 1 位英雄：[1,2]，因为这位英雄的力量为 1，且 monsters[1], monsters[2] <= 1。因此这位英雄收集的金币为 coins[1] + coins[2] = 5 金币。
第 2 位英雄：[1,2,4,5]，因为这位英雄的力量为 4，且 monsters[1], monsters[2], monsters[4], monsters[5] <= 4。因此这位英雄收集的金币为 coins[1] + coins[2] + coins[4] + coins[5] = 16 金币。
第 3 位英雄：[1,2,4]，因为这位英雄的力量为 2，且 monsters[1], monsters[2], monsters[4] <= 2。因此这位英雄收集的金币为 coins[1] + coins[2] + coins[4] = 10 金币。
因此答案为 [5,16,10]。

示例 2：

输入：heroes = [5], monsters = [2,3,1,2], coins = [10,6,5,2]
输出：[23]
解释：这位英雄可以击败所有怪物，因为 monsters[i] <= 5。所以他收集了所有的金币：coins[1] + coins[2] + coins[3] + coins[4] = 23，因此答案为 [23]。

示例 3：

输入：heroes = [4,4], monsters = [5,7,8], coins = [1,1,1]
输出：[0,0]
解释：在这个例子中，没有英雄可以击败怪物。因此答案为 [0,0] 。

 

提示：

  • 1 <= n == heroes.length <= 105
  • 1 <= m == monsters.length <= 105
  • coins.length == m
  • 1 <= heroes[i], monsters[i], coins[i] <= 109

解法

方法一：排序 + 前缀和 + 二分查找

我们可以将怪物和金币按照怪物的战斗力从小到大排序，然后使用前缀和计算每个英雄打败前 $i$ 个怪物可以获得的金币总数。

接下来，对于每个英雄，我们可以使用二分查找找到他可以打败的最大的怪物，然后使用前缀和计算他可以获得的金币总数即可。

时间复杂度 $O((m + n) \times \log n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是怪物和英雄的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maximumCoins(
        self, heroes: List[int], monsters: List[int], coins: List[int]
    ) -> List[int]:
        m = len(monsters)
        idx = sorted(range(m), key=lambda i: monsters[i])
        s = list(accumulate((coins[i] for i in idx), initial=0))
        ans = []
        for h in heroes:
            i = bisect_right(idx, h, key=lambda i: monsters[i])
            ans.append(s[i])
        return ans

 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
class Solution {
    public long[] maximumCoins(int[] heroes, int[] monsters, int[] coins) {
        int m = monsters.length;
        Integer[] idx = new Integer[m];
        for (int i = 0; i < m; ++i) {
            idx[i] = i;
        }

        Arrays.sort(idx, Comparator.comparingInt(j -> monsters[j]));
        long[] s = new long[m + 1];
        for (int i = 0; i < m; ++i) {
            s[i + 1] = s[i] + coins[idx[i]];
        }
        int n = heroes.length;
        long[] ans = new long[n];
        for (int k = 0; k < n; ++k) {
            int i = search(monsters, idx, heroes[k]);
            ans[k] = s[i];
        }
        return ans;
    }

    private int search(int[] nums, Integer[] idx, int x) {
        int l = 0, r = idx.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[idx[mid]] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 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
class Solution {
public:
    vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters, vector<int>& coins) {
        int m = monsters.size();
        vector<int> idx(m);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return monsters[i] < monsters[j];
        });
        long long s[m + 1];
        s[0] = 0;
        for (int i = 1; i <= m; ++i) {
            s[i] = s[i - 1] + coins[idx[i - 1]];
        }
        vector<long long> ans;
        auto search = [&](int x) {
            int l = 0, r = m;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (monsters[idx[mid]] > x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        };
        for (int h : heroes) {
            ans.push_back(s[search(h)]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maximumCoins(heroes []int, monsters []int, coins []int) (ans []int64) {
    m := len(monsters)
    idx := make([]int, m)
    for i := range idx {
        idx[i] = i
    }
    sort.Slice(idx, func(i, j int) bool { return monsters[idx[i]] < monsters[idx[j]] })
    s := make([]int64, m+1)
    for i, j := range idx {
        s[i+1] = s[i] + int64(coins[j])
    }
    for _, h := range heroes {
        i := sort.Search(m, func(i int) bool { return monsters[idx[i]] > h })
        ans = append(ans, s[i])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function maximumCoins(heroes: number[], monsters: number[], coins: number[]): number[] {
    const m = monsters.length;
    const idx: number[] = Array.from({ length: m }, (_, i) => i);
    idx.sort((i, j) => monsters[i] - monsters[j]);
    const s: number[] = Array(m + 1).fill(0);
    for (let i = 0; i < m; ++i) {
        s[i + 1] = s[i] + coins[idx[i]];
    }
    const search = (x: number): number => {
        let l = 0;
        let r = m;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (monsters[idx[mid]] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    return heroes.map(h => s[search(h)]);
}

评论