首页 > 其他分享 >蓄水

蓄水

时间:2023-05-22 23:35:05浏览次数:32  
标签:水缸 int bucket 水桶 蓄水 vat

给定 N 个无限容量且初始均空的水缸,每个水缸配有一个水桶用来打水,第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作:

升级水桶:选择任意一个水桶,使其容量增加为 bucket[i]+1
蓄水:将全部水桶接满水,倒入各自对应的水缸
每个水缸对应最低蓄水量记作 vat[i],返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

注意:实际蓄水量 达到或超过 最低蓄水量,即完成蓄水要求。

示例 1:

输入:bucket = [1,3], vat = [6,8]

输出:4

解释:
第 1 次操作升级 bucket[0];
第 2 ~ 4 次操作均选择蓄水,即可完成蓄水要求。

示例 2:

输入:bucket = [9,0,1], vat = [0,2,2]

输出:3

解释:
第 1 次操作均选择升级 bucket[1]
第 2~3 次操作选择蓄水,即可完成蓄水要求。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/o8SXZn
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        //流方式获取最大水缸容量
        int max = Arrays.stream(vat).max().getAsInt();
        //排除特殊情况
        if (max == 0) {
            return 0;
        }
        //水缸的长度
        int len = vat.length;
        int count = Integer.MAX_VALUE;
        //x代表枚举蓄水次数
        for (int x = 1; x <= max; ++x) {
            //y代表升级水桶次数
            int y = 0;
            //遍历水缸
            for (int i = 0; i < len; ++i) {
                //升级水桶次数=(水缸容量/蓄水次数)
                //(某数+除数-1)=向上取整
                y += Math.max(0, (vat[i] + x - 1) / x - bucket[i]);
            }
            //找到最少操作次数
            count = Math.min(count, x + y);
        }
        return count;
    }
}

标签:水缸,int,bucket,水桶,蓄水,vat
From: https://www.cnblogs.com/xiaochaofang/p/17422050.html

相关文章

  • C# 蓄水池抽样
    C#蓄水池抽样 蓄水池采样算法解决的是在给定但长度未知的大数据集中,随机等概率抽取一个数据。如果知道数据的长度,可以用随机数rand()%n得到一个确切的随机位置,或者分......
  • 蓄水池抽样算法
    不一次性将数据读入内存,只遍历一次数据即可等概率抽取子集数据,真是神奇。测试例子:0到99一百个数字中随机抽取10个数,每个数被抽到概率1/10;重复1000次抽样,结果统计每个数字......