diff options
author | Jack Sangdahl <[email protected]> | 2025-10-08 18:28:37 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-08 18:28:37 -0600 |
commit | b69b6266df7de0ab483d81ba6c9f5fa507aa8972 (patch) | |
tree | ee2de0a6ab220edadec13f1e21c8a25ab63201f6 | |
parent | f3e447ec79036fda15e973ff7d0ea81cbebb4532 (diff) | |
download | leetcode-b69b6266df7de0ab483d81ba6c9f5fa507aa8972.tar.gz leetcode-b69b6266df7de0ab483d81ba6c9f5fa507aa8972.zip |
3494. find the minimum amount of time to brew potions
-rw-r--r-- | find_min_amount_brew_potion.c | 46 | ||||
-rw-r--r-- | find_min_amount_brew_potion.py | 37 |
2 files changed, 83 insertions, 0 deletions
diff --git a/find_min_amount_brew_potion.c b/find_min_amount_brew_potion.c new file mode 100644 index 0000000..31e582b --- /dev/null +++ b/find_min_amount_brew_potion.c @@ -0,0 +1,46 @@ +// 3494. Find the Minimum Amount of Time to Brew Potions +#include "leetcode.h" + +/* + * you are given two integer arrays 'skill' and 'mana' of length 'n' and 'm' + * respectively. in a laboratory, 'n' wizards must brew 'm' potions in order. + * each potion has a mana capacity 'mana[j]' and must pass through all the + * wizards sequentially to be brewed properly. the time taken by the i'th wizard + * on the j'th potion is 'time_ij = skill[i] * mana[j]'. since the brewing + * process is delicate, a potion must be passed to the next wizard immediately + * after the current wizard completes their work. this means the timing must be + * synchronised so that each wizard begins working on a potion exactly when it + * arrives. return the minimum amount of time required for the potions to be + * brewed properly. + */ + +long long minTime(int *skill, int skillSize, int *mana, int manaSize) { + long long *pre = (long long *)calloc(skillSize + 1, sizeof(long long)); + for (int i = 1; i < skillSize; i++) + pre[i] = pre[i - 1] + skill[i]; + long long sum = (long long)skill[0] * mana[0]; + for (int j = 1; j < manaSize; j++) { + long long max = (long long)skill[0] * mana[j]; + for (int i = 1; i < skillSize; i++) { + long long diff = pre[i] * mana[j - 1] - pre[i - 1] * mana[j]; + if (diff > max) + max = diff; + } + sum += max; + } + int ans = pre[skillSize - 1] * mana[manaSize - 1]; + free(pre); + return sum + ans; +} + +int main() { + int s1[] = {1, 5, 2, 4}, m1[] = {5, 1, 4, 2}; + int s2[] = {1, 1, 1}, m2[] = {1, 1, 1}; + int s3[] = {1, 2, 3, 4}, m3[] = {1, 2}; + printf("%lld\n", + minTime(s1, ARRAY_SIZE(s1), m1, ARRAY_SIZE(m1))); // expect: 110 + printf("%lld\n", minTime(s2, ARRAY_SIZE(s2), m2, ARRAY_SIZE(m2))); // expect: + // 5 + printf("%lld\n", + minTime(s3, ARRAY_SIZE(s3), m3, ARRAY_SIZE(m3))); // expect: 21 +} diff --git a/find_min_amount_brew_potion.py b/find_min_amount_brew_potion.py new file mode 100644 index 0000000..ab0c6a6 --- /dev/null +++ b/find_min_amount_brew_potion.py @@ -0,0 +1,37 @@ +# 3494. Find the Minimum Amount of Time to Brew Potions +from itertools import accumulate + +""" +you are given two integer arrays 'skill' and 'mana' of length 'n' and 'm' +respectively. in a laboratory, 'n' wizards must brew 'm' potions in order. +each potion has a mana capacity 'mana[j]' and must pass through all the +wizards sequentially to be brewed properly. the time taken by the i'th wizard +on the j'th potion is 'time_ij = skill[i] mana[j]'. since the brewing +process is delicate, a potion must be passed to the next wizard immediately +after the current wizard completes their work. this means the timing must be +synchronised so that each wizard begins working on a potion exactly when it +arrives. return the minimum amount of time required for the potions to be +brewed properly. +""" + + +class Solution(object): + def minTime(self, skill, mana): + """ + :type skill: List[int] + :type mana: List[int] + :rtype: int + """ + acc, t = list(accumulate(skill, initial=0)), 0 + for j in range(1, len(mana)): + t += max( + mana[j - 1] * acc[i + 1] - mana[j] * acc[i] for i in range(len(skill)) + ) + return t + acc[-1] * mana[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.minTime(skill=[1, 5, 2, 4], mana=[5, 1, 4, 2])) + print(obj.minTime(skill=[1, 1, 1], mana=[1, 1, 1])) + print(obj.minTime(skill=[1, 2, 3, 4], mana=[1, 2])) |