Minimum amount of damage dealt to bob

Array Greedy Sorting

39.6% acceptance

Feb 25, 2026

165

You are given power, damage[i], health[i]. Each second, all alive enemies deal damage to Bob. Bob chooses one enemy and deals power damage to them. Kill time = ceil(health[i]/power). Minimize total damage dealt to Bob. Greedy: sort by damage[i]/kill_time[i] descending (highest DPS priority → kill those first). When killing in order, damage at time t is sum of all still-alive enemies' damage.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_damage(power: i32, damage: Vec<i32>, health: Vec<i32>) -> i64 {
    let n = damage.len();
    let power = power as i64;
    let total_damage: i64 = damage.iter().map(|&d| d as i64).sum();
    
    // kill_time[i] = ceil(health[i] / power)
    let kill_time: Vec<i64> = health.iter().map(|&h| ((h as i64 + power - 1) / power)).collect();
    
    // Sort by damage[i]/kill_time[i] descending ↔ damage[i]*1 / kill_time[i] desc
    // i.e., rank by damage[i] / kill_time[i] descending
    let mut order: Vec<usize> = (0..n).collect();
    order.sort_unstable_by(|&a, &b| {
      // Compare damage[a]/kill_time[a] vs damage[b]/kill_time[b]
      // = damage[a]*kill_time[b] vs damage[b]*kill_time[a] (cross multiply)
      let lhs = damage[b] as i64 * kill_time[a];
      let rhs = damage[a] as i64 * kill_time[b];
      lhs.cmp(&rhs)
    });
    
    let mut ans = 0i64;
    let mut remaining_damage = total_damage;
    let mut t = 0i64;
    for &i in &order {
      t += kill_time[i];
      ans += remaining_damage * kill_time[i];
      remaining_damage -= damage[i] as i64;
    }
    // Actually compute properly: for each enemy killed at time t_i (cumulative),
    // the damage from that kill event is (remaining_at_time - damage[i]) * kill_time[i]
    // Let's redo with correct formula
    // sum_of_damages_while_killing_i = remaining_total_damage_before_killing_i * kill_time[i]
    let _ = t;
    let _ = ans;
    
    let mut ans = 0i64;
    let mut rem = total_damage;
    for &i in &order {
      ans += rem * kill_time[i];
      rem -= damage[i] as i64;
    }
    ans
  }
}