哪个网站比较好,wordpress后台乱了是怎么回事,网页设计与网站建设中的热点是什么,佛山外贸网站建设价位文章目录 相关链接什么时候使用二分答案#xff1f;题目列表最大化最小化相关题目列表#x1f4d5;2439. 最小化数组中的最大值解法1——二分答案解法2——分类讨论O(n) 2513. 最小化两个数组中的最大值#xff08;二分答案lcm容斥原理#xff09;#x1f402;好题#x… 文章目录 相关链接什么时候使用二分答案题目列表最大化最小化相关题目列表2439. 最小化数组中的最大值解法1——二分答案解法2——分类讨论O(n) 2513. 最小化两个数组中的最大值二分答案lcm容斥原理好题相似题目容斥原理二分查找878. 第 N 个神奇数字1201. 丑数 III 2517. 礼盒的最大甜蜜度二分答案 相关链接
【力扣周赛】第 362 场周赛⭐差分匹配状态压缩DP矩阵快速幂优化DPKMP里面有一些二分答案的题目。 【力扣周赛】第 363 场周赛完全平方数和质因数分解 T3是二分答案。
什么时候使用二分答案
看到「最大化最小值」或者「最小化最大值」就要想到二分答案这是一个固定的套路。
或者
答案不好直接求但是可以判断某个数字是否可以满足题目要求且单调时。
具体看下面例题体会一下即可。
题目列表
最大化最小化相关题目列表
题目列表来源https://leetcode.cn/problems/maximize-the-minimum-powered-city/solutions/2050272/er-fen-da-an-qian-zhui-he-chai-fen-shu-z-jnyv/
2439. 最小化数组中的最大值
https://leetcode.cn/problems/minimize-maximum-of-array/
提示 n nums.length 2 n 10^5 0 nums[i] 10^9
解法1——二分答案
class Solution {public int minimizeArrayValue(int[] nums) {int l Integer.MAX_VALUE, r Integer.MIN_VALUE;for (int x: nums) {l Math.min(l, x);r Math.max(r, x);}while (l r) {int mid l r 1;if (check(mid, nums)) r mid;else l mid 1;}return l;}public boolean check(int k, int[] nums) {if (nums[0] k) return false;long d k - nums[0]; // 使用long防止溢出for (int i 1; i nums.length; i) {if (nums[i] k) d k - nums[i];else {d - nums[i] - k;if (d 0) return false;}}return true;}
}解法2——分类讨论O(n)
首先最大值的最小值是 nums[0]。 对于 nums[1]当其 nums[0] 时答案还是 nums[0]当其 nums[0] 时则答案是两者的平均向上取整。
class Solution {public int minimizeArrayValue(int[] nums) {long mx 0, sum 0;for (int i 0; i nums.length; i) {sum nums[i];// (sum i) / (i 1) 是因为要向上取整mx Math.max(mx, (sum i) / (i 1)); }return (int)mx;}
}2513. 最小化两个数组中的最大值二分答案lcm容斥原理好题
https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/
提示 2 divisor1, divisor2 10^5 1 uniqueCnt1, uniqueCnt2 10^9 2 uniqueCnt1 uniqueCnt2 10^9
二分答案。
class Solution {public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {long l 0, r (long)Integer.MAX_VALUE;while (l r) {long mid l r 1;// 两个数组不能选择的数字数量long x mid / divisor1, y mid / divisor2, z mid / lcm(divisor1, divisor2);long sum uniqueCnt1 uniqueCnt2 z; // 至少需要的数字数量// arr1不能使用的看arr2能不能使用反之同理sum Math.max(0, x - z - uniqueCnt2) Math.max(0, y - z - uniqueCnt1);if (sum mid) r mid;else l mid 1;}return (int)l;}// 最小公倍数public long lcm(long x, long y) {return x / gcd(x, y) * y;}// 最大公因数public long gcd(long x, long y) {return y 0? x: gcd(y, x % y);}
}相似题目容斥原理二分查找
878. 第 N 个神奇数字
https://leetcode.cn/problems/nth-magical-number/ 答案可能会很大所以先将变量设置成 long 类型。
class Solution {final long MOD (long)1e9 7;public int nthMagicalNumber(int n, int a, int b) {long c lcm(a, b);long l 2, r Long.MAX_VALUE - 2;while (l r) {long mid l r 1;long x mid / a, y mid / b, z mid / c;long s x y - z; // 容斥原理if (s n) l mid 1;else r mid;}return (int)(l % MOD);}public long lcm(long a, long b) {return a * b / gcd(a, b);}public long gcd(long a, long b) {return b 0? a: gcd(b, a % b);}
}1201. 丑数 III
https://leetcode.cn/problems/ugly-number-iii/description/ 提示 1 n, a, b, c 10^9 1 a * b * c 10^18 本题结果在 [1, 2 * 10^9] 的范围内
注意这题也要先使用 long 数据类型。
class Solution {public int nthUglyNumber(int n, int a, int b, int c) {// 注意要转成longlong x lcm(a, b), y lcm(b, c), z lcm(a, c), q lcm(x, y);long l 1, r (long)2e9;while (l r) {long mid l r 1;long aa mid / a, bb mid / b, cc mid / c, xx mid / x, yy mid / y, zz mid / z, qq mid / q;// 容斥原理long s aa bb cc - xx - yy - zz qq;if (s n) l mid 1;else r mid;}return (int)l;}// 求最小公倍数public long lcm(long a, long b) {return a / gcd(a, b) * b;}// 求最大公因数public long gcd(long a, long b) {return b 0? a: gcd(b, a % b);}
}2517. 礼盒的最大甜蜜度二分答案
https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/ 提示 2 k price.length 10^5 1 price[i] 10^9
class Solution {public int maximumTastiness(int[] price, int k) {Arrays.sort(price);int n price.length, l 0, r price[n - 1] - price[0];while (l r) {int mid l r 1 1;int s 1, last price[0];for (int i 1; i n s k; i) {if (price[i] - last mid) {s;last price[i];}}if (s k) r mid - 1;else l mid;}return l;}
}
文章转载自： http://www.morning.lzqdd.cn.gov.cn.lzqdd.cn http://www.morning.twpq.cn.gov.cn.twpq.cn http://www.morning.lgrkr.cn.gov.cn.lgrkr.cn http://www.morning.lsmnn.cn.gov.cn.lsmnn.cn http://www.morning.ncrk.cn.gov.cn.ncrk.cn http://www.morning.nuejun.com.gov.cn.nuejun.com http://www.morning.dmjhp.cn.gov.cn.dmjhp.cn http://www.morning.dxsyp.cn.gov.cn.dxsyp.cn http://www.morning.mbdbe.cn.gov.cn.mbdbe.cn http://www.morning.cgthq.cn.gov.cn.cgthq.cn http://www.morning.jpgfx.cn.gov.cn.jpgfx.cn http://www.morning.xxzjb.cn.gov.cn.xxzjb.cn http://www.morning.lqjpb.cn.gov.cn.lqjpb.cn http://www.morning.cyjjp.cn.gov.cn.cyjjp.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn http://www.morning.dwwlg.cn.gov.cn.dwwlg.cn http://www.morning.ntqjh.cn.gov.cn.ntqjh.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.xsqbx.cn.gov.cn.xsqbx.cn http://www.morning.wdykx.cn.gov.cn.wdykx.cn http://www.morning.zwyuan.com.gov.cn.zwyuan.com http://www.morning.bsghk.cn.gov.cn.bsghk.cn http://www.morning.dfygx.cn.gov.cn.dfygx.cn http://www.morning.dfkmz.cn.gov.cn.dfkmz.cn http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.stlgg.cn.gov.cn.stlgg.cn http://www.morning.lqgtx.cn.gov.cn.lqgtx.cn http://www.morning.mzmqg.cn.gov.cn.mzmqg.cn http://www.morning.sfnr.cn.gov.cn.sfnr.cn http://www.morning.qghjc.cn.gov.cn.qghjc.cn http://www.morning.mcmpq.cn.gov.cn.mcmpq.cn http://www.morning.lzqnj.cn.gov.cn.lzqnj.cn http://www.morning.tgfjm.cn.gov.cn.tgfjm.cn http://www.morning.slwfy.cn.gov.cn.slwfy.cn http://www.morning.csznh.cn.gov.cn.csznh.cn http://www.morning.pngph.cn.gov.cn.pngph.cn http://www.morning.nrfqd.cn.gov.cn.nrfqd.cn http://www.morning.mgkcz.cn.gov.cn.mgkcz.cn http://www.morning.mmxt.cn.gov.cn.mmxt.cn http://www.morning.dfhkh.cn.gov.cn.dfhkh.cn http://www.morning.cybch.cn.gov.cn.cybch.cn http://www.morning.yhgbd.cn.gov.cn.yhgbd.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.tnwwl.cn.gov.cn.tnwwl.cn http://www.morning.nxnrt.cn.gov.cn.nxnrt.cn http://www.morning.lmnbp.cn.gov.cn.lmnbp.cn http://www.morning.qqbjt.cn.gov.cn.qqbjt.cn http://www.morning.blfgh.cn.gov.cn.blfgh.cn http://www.morning.mqgqf.cn.gov.cn.mqgqf.cn http://www.morning.bnpn.cn.gov.cn.bnpn.cn http://www.morning.rshs.cn.gov.cn.rshs.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.bsbcp.cn.gov.cn.bsbcp.cn http://www.morning.ghfmd.cn.gov.cn.ghfmd.cn http://www.morning.lzqdl.cn.gov.cn.lzqdl.cn http://www.morning.slnz.cn.gov.cn.slnz.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.yznsx.cn.gov.cn.yznsx.cn http://www.morning.dwncg.cn.gov.cn.dwncg.cn http://www.morning.nkddq.cn.gov.cn.nkddq.cn http://www.morning.qkqzm.cn.gov.cn.qkqzm.cn http://www.morning.rmpkn.cn.gov.cn.rmpkn.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.wrtsm.cn.gov.cn.wrtsm.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.ldzxf.cn.gov.cn.ldzxf.cn http://www.morning.mlfmj.cn.gov.cn.mlfmj.cn http://www.morning.njftk.cn.gov.cn.njftk.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.qcslh.cn.gov.cn.qcslh.cn http://www.morning.rpgdd.cn.gov.cn.rpgdd.cn http://www.morning.tsmxh.cn.gov.cn.tsmxh.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.wlbwp.cn.gov.cn.wlbwp.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.gqflj.cn.gov.cn.gqflj.cn http://www.morning.kdbcx.cn.gov.cn.kdbcx.cn http://www.morning.jfmjq.cn.gov.cn.jfmjq.cn http://www.morning.mmclj.cn.gov.cn.mmclj.cn
