微网站建设图片,推荐优秀的企业网站设计,如何写代码做网站6,推荐十个网站2024.1.27 题目来源我的题解方法一 二分查找 题目来源
力扣每日一题#xff1b;题序#xff1a;2861
我的题解
方法一 二分查找 使用二分查找#xff0c;下界为0#xff0c;上界因为预算和已有金属最大上限是 1 0 8 10^8 108#xff0c;所以设置二分查找上界为2* 1 0 8… 2024.1.27 题目来源我的题解方法一 二分查找 题目来源
力扣每日一题题序2861
我的题解
方法一 二分查找 使用二分查找下界为0上界因为预算和已有金属最大上限是 1 0 8 10^8 108所以设置二分查找上界为2* 1 0 8 10^8 108 时间复杂度O(nklogC)其中 C 是答案的范围。二分查找需要的次数为 O(logC)每一次需要 O(nk)的时间进行判断。 空间复杂度O(1) public int maxNumberOfAlloys(int n, int k, int budget, ListListInteger composition, ListInteger stock, ListInteger cost) {int left0,right200000000,res0;while(leftright){int mid((right-left)1)left;boolean hasValidfalse;//用于标识是否有机器可以产mid个合金//判断每一个机器for(int i0;ik;i){if(check(n,composition,stock,cost,i,mid)budget){hasValidtrue;break;}}if(hasValid){resmid;leftmid1;}else{rightmid-1;}}return res;
}
public long check(int n,ListListInteger composition, ListInteger stock, ListInteger cost,int i,int mid){long need0;for(int j0;jn;j){needMath.max((long)composition.get(i).get(j)*mid-stock.get(j),0)*cost.get(j);}return need;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
