3273. Minimum Amount of Damage Dealt to Bob Hard

1/**
2 * [3273] Minimum Amount of Damage Dealt to Bob
3 *
4 * You are given an integer power and two integer arrays damage and health, both having length n.
5 * Bob has n enemies, where enemy i will deal Bob damage[i] points of damage per second while they are alive (i.e. health[i] > 0).
6 * Every second, after the enemies deal damage to Bob, he chooses one of the enemies that is still alive and deals power points of damage to them.
7 * Determine the minimum total amount of damage points that will be dealt to Bob before all n enemies are dead.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">power = 4, damage = [1,2,3,4], health = [4,5,6,8]</span>
12 * Output: <span class="example-io">39</span>
13 * Explanation:
14 * 
15 * 	Attack enemy 3 in the first two seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is 10 + 10 = 20 points.
16 * 	Attack enemy 2 in the next two seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is 6 + 6 = 12 points.
17 * 	Attack enemy 0 in the next second, after which enemy 0 will go down, the number of damage points dealt to Bob is 3 points.
18 * 	Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is 2 + 2 = 4 points.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">power = 1, damage = [1,1,1,1], health = [1,2,3,4]</span>
23 * Output: <span class="example-io">20</span>
24 * Explanation:
25 * 
26 * 	Attack enemy 0 in the first second, after which enemy 0 will go down, the number of damage points dealt to Bob is 4 points.
27 * 	Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is 3 + 3 = 6 points.
28 * 	Attack enemy 2 in the next three seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is 2 + 2 + 2 = 6 points.
29 * 	Attack enemy 3 in the next four seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is 1 + 1 + 1 + 1 = 4 points.
30 * </div>
31 * <strong class="example">Example 3:
32 * <div class="example-block">
33 * Input: <span class="example-io">power = 8, damage = [40], health = [59]</span>
34 * Output: <span class="example-io">320</span>
35 * </div>
36 *  
37 * Constraints:
38 * 
39 * 	1 <= power <= 10^4
40 * 	1 <= n == damage.length == health.length <= 10^5
41 * 	1 <= damage[i], health[i] <= 10^4
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/minimum-amount-of-damage-dealt-to-bob/
47// discuss: https://leetcode.com/problems/minimum-amount-of-damage-dealt-to-bob/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn min_damage(power: i32, damage: Vec<i32>, health: Vec<i32>) -> i64 {
53        
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3273() {
65    }
66}
67