2861. 最大合金数 (opens new window)

1.二分查找

题目限定所有合金都需要由同一台机器制造，因此需要枚举每一种机器，计算得到最多的合金数量。

在限定每一种合金花费所有金属的情况下，计算最大的数量，使其正好花费完所有的库存+经费。同一个合金制作时会耗尽需要的所有金属，不存在优化；且资源调度上有库存先用库存，不够再用经。

因此整个问题只有合金数量是自变量，因此很容易想到使用二分进行枚举。

• 合金数量越多，消耗的资源和资金越大
• 合金数量越少，消耗的资源和资金越小

class Solution {
    public int maxNumberOfAlloys(int n, int k1, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int maxStock=Integer.MIN_VALUE;
        for(int i=0;i<stock.size();i++){
            maxStock=Math.max(maxStock,stock.get(i));
        }

        int res=0;
        //枚举每一个机器
        for(int i=0;i<composition.size();i++){
            //估计最大购买量上界=（最大库存+最大材料购买量）/最小合金构造装备
            int low=0,high=maxStock+budget;
            List<Integer> need=composition.get(i);
            while(low<high){
                int mid=(low+high)>>1;
                //计算制造当前数量合金消费的总金额
                long costTmp=0;
                for(int k=0;k<need.size();k++){
                    long matNum=(long)need.get(k)*mid;
                    if(matNum>stock.get(k)){
                        costTmp+=(long)(matNum-stock.get(k))*cost.get(k);
                    }
                }
                if(costTmp<=budget) low=mid+1;
                else high=mid;
                if(low==high){
                    long costTmp2=0;
                    for(int k=0;k<need.size();k++){
                        long matNum=(long)need.get(k)*low;
                        if(matNum>stock.get(k)){
                            costTmp2+=(long)(matNum-stock.get(k))*cost.get(k);
                        }
                    }
                    if(costTmp2>budget)low--;
                    break;
                }
            }
            res=Math.max(res,low);

        }
        return res;
    }
}