BS:最大化最小值

2024-01-01 19:45:19

和最小化最大值是一回事,二分板子。

1. LC 1552 两球之间的磁力

灵神这题给的1920分。但貌似很简单?之前做一道子集状压DP的分数是1887,感觉难度比这个难多了。

单调性:

对于任意最小磁力m

  1. 假设以m为间隔长度放置球可以把球放完,那么以<m为间隔放置球也一定能放完。
  2. 假设以m为间隔长度放置球不能把球放完,那么以>m为间隔放置球也不能放完。

上限:可以先把position排个序。(position[n-1] - position[0])/(m-1)即为最长间隔(因为我们的目标是能把球放完)

下限:0(题目没说球不能放同一个篮子)

检查:

暴力模拟即可。一般二分的思维含量就在检查上,所以我觉得这题不足1920分的原因就是因为检查实在太简单。

import java.util.Arrays;

class Solution {
    public int maxDistance(int[] position, int m) {
        int lp,rp,mid,ans;
        ans = -1;
        int n = position.length;
        Arrays.sort(position);
        lp = 0;
        rp = (position[n-1]-position[0])/(m-1)+1;
        while(lp<rp){
            mid = ((rp-lp)>>>1)+lp;
            if(check(position,mid,m)){
                ans = mid;
                lp = mid+1;
            }else{
                rp = mid;
            }
        }
        return ans;
    }

    private boolean check(int[] position,int mid,int m){
        m--;
        int prev = position[0];
        for(int i=1;i<position.length;i++){
            if(position[i]-prev>=mid){
                m--;
                if(m<=0) return true;
                prev = position[i];
            }
        }
        return m<=0;
    }
}

2. LC 2861 最大合金数

这题读错题了。我以为是多个机器都可以用,求最大合金数,直接变成背包问题。没想到是每次只能挑一台机器用。那就很好做了。

单调性:对于某台机器P,对于任意最大合金数m

  1. 假设可以制造m个合金,那么也一定能制造<m个合金(大不了多了不造了)
  2. 假设无法制造m个合金,那么也一定不能制造>m个合金

上限:库存资金拉满1e8,耗材最小1,那么就是1e8*2

下限:一个不造,0

检查:

暴力模拟即可

import java.util.*;
class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        long lp,rp,mid,ans,tmp;
        ans = -1;
        // 读错题了,由于所有合金都需要用同一台机器制造,因此检查每台机器的最大值,然后再取个最大值即可
        for (List<Integer> demand : composition) {
            tmp = -1;
            lp = 0;
            // 库存资金拉满1e8,假设耗材都是1,顶上就是2*1e8
            rp = (long) (2*1e8+1);
            while(lp<rp){
                mid = ((rp-lp)>>>1)+lp;
                if(check(budget,demand,stock,cost,mid)){
                    tmp = mid;
                    lp = mid+1;
                }else{
                    rp = mid;
                }
            }
            ans = Math.max(tmp,ans);
        }
        return (int) ans;
    }

    private boolean check(int budget,List<Integer> demand,List<Integer> stock,List<Integer> cost,long mid){
        long money = 0L;
        for (int i = 0; i < demand.size(); i++) {
            long need = mid * demand.get(i);
            Integer stk = stock.get(i);
            if(stk < need){
                // 已有库存不够用
                money += (need- stk)*cost.get(i);
                if(money>budget){
                    return false;
                }
            }
        }
        return money<=budget;
    }
}

文章来源:https://blog.csdn.net/lyh20021209/article/details/135315088
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。