Question

2838. Maximum Coins Heroes Can Collect

English Version

题目描述

There is a battle and n heroes are trying to defeat m monsters. You are given two 1-indexed arrays of positive integers heroes and monsters of length n and m, respectively. heroes[i] is the power of ith hero, and monsters[i] is the power of ith monster.

The ith hero can defeat the jth monster if monsters[j] <= heroes[i].

You are also given a 1-indexed array coins of length m consisting of positive integers. coins[i] is the number of coins that each hero earns after defeating the ith monster.

Return_ an array _ans_ of length _n_ where _ans[i]_ is the maximum number of coins that the _ith_ hero can collect from this battle_.

Notes

• The health of a hero doesn't get reduced after defeating a monster.
• Multiple heroes can defeat a monster, but each monster can be defeated by a given hero only once.

 

Example 1:

Input: heroes = [1,4,2], monsters = [1,1,5,2,3], coins = [2,3,4,5,6]
Output: [5,16,10]
Explanation: For each hero, we list the index of all the monsters he can defeat:
1st hero: [1,2] since the power of this hero is 1 and monsters[1], monsters[2] <= 1. So this hero collects coins[1] + coins[2] = 5 coins.
2nd hero: [1,2,4,5] since the power of this hero is 4 and monsters[1], monsters[2], monsters[4], monsters[5] <= 4. So this hero collects coins[1] + coins[2] + coins[4] + coins[5] = 16 coins.
3rd hero: [1,2,4] since the power of this hero is 2 and monsters[1], monsters[2], monsters[4] <= 2. So this hero collects coins[1] + coins[2] + coins[4] = 10 coins.
So the answer would be [5,16,10].

Example 2:

Input: heroes = [5], monsters = [2,3,1,2], coins = [10,6,5,2]
Output: [23]
Explanation: This hero can defeat all the monsters since monsters[i] <= 5. So he collects all of the coins: coins[1] + coins[2] + coins[3] + coins[4] = 23, and the answer would be [23].

Example 3:

Input: heroes = [4,4], monsters = [5,7,8], coins = [1,1,1]
Output: [0,0]
Explanation: In this example, no hero can defeat a monster. So the answer would be [0,0],

 

Constraints:

• 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$ 分别是怪物和英雄的数量。

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

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;
  }
}

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;
  }
};

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
}

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)]);
}