typescript 解法, 执行用时: 124 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-27 14:35:25

function storeWater(bucket: number[], vat: number[]): number {
    const mx = Math.max(...vat);
    if (mx === 0) {
        return 0;
    }
    const n = vat.length;
    let ans = 1 << 30;
    for (let x = 1; x <= mx; ++x) {
        let y = 0;
        for (let i = 0; i < n; ++i) {
            y += Math.max(0, Math.ceil(vat[i] / x) - bucket[i]);
        }
        ans = Math.min(ans, x + y);
    }
    return ans;
}

cpp 解法, 执行用时: 132 ms, 内存消耗: 8.2 MB, 提交时间: 2023-09-27 14:35:11

class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int mx = *max_element(vat.begin(), vat.end());
        if (mx == 0) {
            return 0;
        }
        int ans = 1 << 30;
        int n = bucket.size();
        for (int x = 1; x <= mx; ++x) {
            int y = 0;
            for (int i = 0; i < n; ++i) {
                y += max(0, (vat[i] + x - 1) / x - bucket[i]);
            }
            ans = min(ans, x + y);
        }
        return ans;
    }
};

java 解法, 执行用时: 58 ms, 内存消耗: 38.7 MB, 提交时间: 2023-09-27 14:34:56

class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int mx = Arrays.stream(vat).max().getAsInt();
        if (mx == 0) {
            return 0;
        }
        int n = vat.length;
        int ans = 1 << 30;
        for (int x = 1; x <= mx; ++x) {
            int y = 0;
            for (int i = 0; i < n; ++i) {
                y += Math.max(0, (vat[i] + x - 1) / x - bucket[i]);
            }
            ans = Math.min(ans, x + y);
        }
        return ans;
    }
}

python3 解法, 执行用时: 3552 ms, 内存消耗: 16 MB, 提交时间: 2023-09-27 14:34:32

class Solution:
    # 贪心，优先升级水桶
    def storeWater(self, bucket: List[int], vat: List[int]) -> int:
        mx = max(vat)
        if mx == 0: return 0
        ans = inf
        for x in range(1, mx + 1):
            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))
            ans = min(ans, x + y)
        return ans

golang 解法, 执行用时: 212 ms, 内存消耗: 2.3 MB, 提交时间: 2021-06-07 16:16:11

func storeWater(bucket []int, vat []int) int {
	max := 0
	for _, v := range vat {
		if max < v {
			max = v
		}
	}
	if max == 0 {
		return 0
	}
	n := len(bucket)
	ans := math.MaxInt32
	for i := 1; i <= max; i++ {
		//每次倒水量
		per := 0
		//倒水i次，所以操作次数+i
		cur := i
		//遍历每个水缸
		for j := 0; j < n; j++ {
			// 水槽容量/倒水次数=每次倒水量
			per = (vat[j] + i - 1) / i
			// 每次倒水量-初始水量=需要升级次数
			if per-bucket[j] > 0 {
				cur += per - bucket[j]
			}
		}
		//所有倒水次数中，取最小的操作次数
		if ans > cur {
			ans = cur
		}
	}

	return ans
}