Skip to content

3273. Minimum Amount of Damage Dealt to Bob 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 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
struct Enemy {
  int damage;
  int timeTakenDown;
};

class Solution {
 public:
  long long minDamage(int power, vector<int>& damage, vector<int>& health) {
    long ans = 0;
    long sumDamage = accumulate(damage.begin(), damage.end(), 0L);
    vector<Enemy> enemies;

    for (int i = 0; i < damage.size(); ++i)
      enemies.emplace_back(damage[i], (health[i] + power - 1) / power);

    // It's better to take down the enemy i first if the damage dealt of taking
    // down i first is less than the damage dealt of taking down j first. So,
    //    damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
    //    damage[j] * t[j] + (t[i] + t[j]) * damage[i]
    // => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
    //    damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
    // => damage[j] * t[i] < damage[i] * t[j]
    // => damage[j] / t[j] < damage[i] / t[i]
    ranges::sort(enemies, ranges::greater{}, [](const Enemy& e) {
      return static_cast<double>(e.damage) / e.timeTakenDown;
    });

    for (const Enemy& enemy : enemies) {
      ans += sumDamage * enemy.timeTakenDown;
      sumDamage -= enemy.damage;
    }

    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
36
37
38
39
class Enemy {
  public int damage;
  public int timeTakenDown;
  public Enemy(int damage, int timeTakenDown) {
    this.damage = damage;
    this.timeTakenDown = timeTakenDown;
  }
}

class Solution {
  public long minDamage(int power, int[] damage, int[] health) {
    long ans = 0;
    long sumDamage = Arrays.stream(damage).asLongStream().sum();
    Enemy[] enemies = new Enemy[damage.length];

    for (int i = 0; i < damage.length; ++i)
      enemies[i] = new Enemy(damage[i], (health[i] + power - 1) / power);

    // It's better to take down the enemy i first if the damage dealt of taking
    // down i first is less than the damage dealt of taking down j first. So,
    //    damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
    //    damage[j] * t[j] + (t[i] + t[j]) * damage[i]
    // => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
    //    damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
    // => damage[j] * t[i] < damage[i] * t[j]
    // => damage[j] / t[j] < damage[i] / t[i]
    Arrays.sort(enemies,
                (a, b)
                    -> Double.compare((double) b.damage / b.timeTakenDown,
                                      (double) a.damage / a.timeTakenDown));

    for (final Enemy enemy : enemies) {
      ans += sumDamage * enemy.timeTakenDown;
      sumDamage -= enemy.damage;
    }

    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
from dataclasses import dataclass


@dataclass(frozen=True)
class Enemy:
  damage: int
  timeTakenDown: int


class Solution:
  def minDamage(self, power: int, damage: list[int], health: list[int]) -> int:
    ans = 0
    sumDamage = sum(damage)
    enemies = [Enemy(d, (h + power - 1) // power)
               for d, h in zip(damage, health)]

    # It's better to take down the enemy i first if the damage dealt of taking
    # down i first is less than the damage dealt of taking down j first. So,
    #    damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
    #    damage[j] * t[j] + (t[i] + t[j]) * damage[i]
    # => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
    #    damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
    # => damage[j] * t[i] < damage[i] * t[j]
    # => damage[j] / t[j] < damage[i] / t[i]
    enemies.sort(key=lambda x: -x.damage / x.timeTakenDown)

    for enemy in enemies:
      ans += sumDamage * enemy.timeTakenDown
      sumDamage -= enemy.damage

    return ans