Skip to content

Latest commit

 

History

History
386 lines (324 loc) · 10.3 KB

README_EN.md

File metadata and controls

386 lines (324 loc) · 10.3 KB
comments difficulty edit_url tags
true
Hard
Bit Manipulation
Array
Dynamic Programming
Bitmask

2403. Minimum Time to Kill All Monsters 🔒

中文文档

Description

You are given an integer array power where power[i] is the power of the ith monster.

You start with 0 mana points, and each day you increase your mana points by gain where gain initially is equal to 1.

Each day, after gaining gain mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:

  • your mana points will be reset to 0, and
  • the value of gain increases by 1.

Return the minimum number of days needed to defeat all the monsters.

 

Example 1:

Input: power = [3,1,4]
Output: 4
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points.
- Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
- Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster.
It can be proven that 4 is the minimum number of days needed.

Example 2:

Input: power = [1,1,4]
Output: 4
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 4 is the minimum number of days needed.

Example 3:

Input: power = [1,2,4,9]
Output: 6
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points.
- Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster.
- Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 6 is the minimum number of days needed.

 

Constraints:

  • 1 <= power.length <= 17
  • 1 <= power[i] <= 109

Solutions

Solution 1: State Compression + Memorization Search or Dynamic Programming

Since defeating monsters can increase the daily magic power gain $gain$, the order of defeating monsters affects the result, so we need to enumerate. Noting that the data range of the problem is small, we consider using state compression dynamic programming to solve it.

We define a state $mask$ to represent the current situation of defeating monsters. In its binary representation, $1$ represents the monsters that have been defeated, and $0$ represents the monsters that have not been defeated.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(2^n)$. Here, $n$ is the number of monsters.

Python3

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        @cache
        def dfs(mask):
            cnt = mask.bit_count()
            if cnt == len(power):
                return 0
            ans = inf
            for i, v in enumerate(power):
                if mask & (1 << i):
                    continue
                ans = min(ans, dfs(mask | 1 << i) + (v + cnt) // (cnt + 1))
            return ans

        return dfs(0)

Java

class Solution {
    private int n;
    private long[] f;
    private int[] power;

    public long minimumTime(int[] power) {
        n = power.length;
        f = new long[1 << n];
        Arrays.fill(f, -1);
        this.power = power;
        return dfs(0);
    }

    private long dfs(int mask) {
        if (f[mask] != -1) {
            return f[mask];
        }
        int cnt = Integer.bitCount(mask);
        if (cnt == n) {
            return 0;
        }
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (((mask >> i) & 1) == 1) {
                continue;
            }
            ans = Math.min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1));
        }
        f[mask] = ans;
        return ans;
    }
}

C++

using ll = long long;

class Solution {
public:
    vector<ll> f;
    vector<int> power;
    int n;

    long long minimumTime(vector<int>& power) {
        n = power.size();
        f.assign(1 << n, -1);
        this->power = power;
        return dfs(0);
    }

    ll dfs(int mask) {
        if (f[mask] != -1) return f[mask];
        int cnt = __builtin_popcount(mask);
        if (cnt == n) return 0;
        ll ans = LONG_MAX;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) continue;
            ans = min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1));
        }
        f[mask] = ans;
        return ans;
    }
};

Go

func minimumTime(power []int) int64 {
	n := len(power)
	f := make([]int64, 1<<n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(mask int) int64
	dfs = func(mask int) int64 {
		if f[mask] != -1 {
			return f[mask]
		}
		cnt := bits.OnesCount(uint(mask))
		if cnt == n {
			return 0
		}
		var ans int64 = math.MaxInt64
		for i, v := range power {
			if (mask >> i & 1) == 1 {
				continue
			}
			ans = min(ans, dfs(mask|1<<i)+int64((v+cnt)/(cnt+1)))
		}
		f[mask] = ans
		return ans
	}
	return dfs(0)
}

TypeScript

function minimumTime(power: number[]): number {
    const n = power.length;
    const f = new Array(1 << n).fill(-1);
    function dfs(mask) {
        if (f[mask] != -1) {
            return f[mask];
        }
        const cnt = bitCount(mask);
        if (cnt == n) {
            return 0;
        }
        let ans = Infinity;
        for (let i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                continue;
            }
            ans = Math.min(ans, dfs(mask | (1 << i)) + Math.ceil(power[i] / (cnt + 1)));
        }
        f[mask] = ans;
        return ans;
    }
    return dfs(0);
}

function bitCount(x) {
    let cnt = 0;
    for (let i = 0; i < 32; ++i) {
        if ((x >> i) & 1) {
            ++cnt;
        }
    }
    return cnt;
}

Solution 2

Python3

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n = len(power)
        dp = [inf] * (1 << n)
        dp[0] = 0
        for mask in range(1, 1 << n):
            cnt = mask.bit_count()
            for i, v in enumerate(power):
                if (mask >> i) & 1:
                    dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (v + cnt - 1) // cnt)
        return dp[-1]

Java

class Solution {
    public long minimumTime(int[] power) {
        int n = power.length;
        long[] dp = new long[1 << n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;
        for (int mask = 1; mask < 1 << n; ++mask) {
            int cnt = Integer.bitCount(mask);
            for (int i = 0; i < n; ++i) {
                if (((mask >> i) & 1) == 1) {
                    dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + (power[i] + cnt - 1) / cnt);
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}

C++

class Solution {
public:
    long long minimumTime(vector<int>& power) {
        int n = power.size();
        vector<long long> dp(1 << n, LONG_MAX);
        dp[0] = 0;
        for (int mask = 1; mask < 1 << n; ++mask) {
            int cnt = __builtin_popcount(mask);
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (power[i] + cnt - 1) / cnt);
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

Go

func minimumTime(power []int) int64 {
	n := len(power)
	dp := make([]int64, 1<<n)
	for i := range dp {
		dp[i] = math.MaxInt64
	}
	dp[0] = 0
	for mask := 1; mask < 1<<n; mask++ {
		cnt := bits.OnesCount(uint(mask))
		for i, v := range power {
			if ((mask >> i) & 1) == 1 {
				dp[mask] = min(dp[mask], dp[mask^(1<<i)]+int64((v+cnt-1)/cnt))
			}
		}
	}
	return dp[len(dp)-1]
}

TypeScript

function minimumTime(power: number[]): number {
    const n = power.length;
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    for (let mask = 1; mask < 1 << n; ++mask) {
        const cnt = bitCount(mask);
        for (let i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + Math.ceil(power[i] / cnt));
            }
        }
    }
    return dp[dp.length - 1];
}

function bitCount(x) {
    let cnt = 0;
    for (let i = 0; i < 32; ++i) {
        if ((x >> i) & 1) {
            ++cnt;
        }
    }
    return cnt;
}