先就这么写写完过后举例3个数据分别假设这三个数据是答案当既不会出现死循环又能输出正确答案那就是对的eg.找到4是一个答案lmid1。如果5不是答案 和 如果5是答案 看看能不能退出循环二分查找的应用----二分答案(猜答案)步骤1.确定题目是二分的题目 2.确定答案的范围 3.假定中间位置是否可行 4.通过判断不断二分缩小范围题型1.求最值 ----可能用二分2.最小化最大值 3.最大化最小值 ----一定用二分求最值例题1P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷时间复杂度 O(n*lg(r-l))#includeiostream #includecmath using namespace std; int tree[1000005]; //每棵树的高度 int N;long M; //树的个数所需木材(1≤M≤2×10^9,刚好int) bool check(int mid, int maxh) { //cout mid mid ; 调试 long long sum 0; //可能超过int // for (int i 1; i maxh; i) { 数组和下标都弄混淆了 // if (mid h[i]) { // sum h[i] - mid; // } // } //cout sum sum ,M M ; for (int i 1; i N; i) { if (mid tree[i]) { sum tree[i] - mid; } } if (sum M) return true; else return false; } int main() { cin N M; int maxh 0; for (int i 1; i N; i) { cin tree[i]; maxh max(maxh, tree[i]); } //二分区间 int l 0, r maxh; int ans 0; while (l r) { int mid (l r) / 2; if (check(mid,maxh)) { //若合法因为找最大值所以先记录答案再往更大的方向找 ans max(ans, mid); l mid 1; } else { r mid - 1; } } cout ans; }最大化最小值和最小化最大值最小化最大值 在5个班里面最高的个子中挑一个最矮的最大化最小值 在5个班里面最矮的个子中挑一个最高的最大化最小值题目 某个情景求一个最大化最小值二分最小值[l,r] mid---最小值----反推题目给出的另一个条件-----(如果不满足说明还不够小往小方向取如果满足再增大(最大化最小值)看能不能更大化)最大化最小值题目满足 最大化不满足减小化2.例题P2678 [NOIP 2015 提高组] 跳石头 - 洛谷最大化最小值题目满足则最大化不满足则 减小化 (注意这点)Q1:什么叫做最短跳跃距离2Q2:什么叫做最短跳跃距离最大化题目允许你移走岩石这样会改变岩石的分布于是就会得到新的最短距离。移走一个时移走两个时(m) … 求出一个最短距离最大的数。Q3: 确定跳跃距离的范围(每个岩石都是挨着的) 1 ~~ L (直接跳到终点) mid(1L)/2 然后得找大于等于mid的岩石如果两个岩石之间的距离大于mid不动。如果AB距离小于了mid要移动(因为mid一定是最短移动距离)那问题是移动A还是移动B?1.A是起点移动B 2.B是终点移动A 3.A,B在中间A/BQ4:如果发现移动的岩石大于了m,那说明mid怎么样说明mid取大了因为小于mid的才会被移动mid太大了就会导致岩石移的多最大化最小值题目满足则最大化不满足则 减小化往左走二分找7。 7还大了找44时刚好移走m 求的是最大化刚好移动m时是最大化最小值Q5怎么去比较两个岩石之间的距离和统计移走岩石数目两个指针now,和next。now指向岩石起点next往右走判断之间的距离如果小于midcnt(怎样移走在代码中不用体现出来)。如果大于midnow才移动到next的位置时间复杂度 O(nlgL)#includeiostream using namespace std; int S, N, M; //距离起点终点之间的岩石数至多移走的 int dis[50005]; //统计每个点到起点的距离. 下标N1 //int res[1000000005]; //答案数组 bool check(int mid)//判断合不合法即是否移走不多于M块岩石 { //双指针 int now 0, next 0; //两块岩石的起点终点 int cnt0; //统计移走的数目 for (next 1; next N 1; next) { if (mid dis[next] - dis[now]) { cnt; //代码中不用体现岩石是怎么移走的 } else { //距离合法now可以移动过去了 now next; } if (cnt M) break; } if (cnt M) return true; else return false; } int main() { cin S N M; dis[0] 0; //起点 dis[N 1] S; //终点 for (int i1; i N; i) { cin dis[i]; } //答案区间1~~S //二分法 int l 1, r S; int ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans max(ans, mid); //可能是答案保存下来 l mid 1; } else r mid - 1; } cout ans; }总结题目类型1.求最值2.最大化最小值/最小化最大值3.用于枚举优化----logn另外注意二分的代码不唯一四个地方要配合起来只要不出现死循环就行----方法拿三个数据去模拟一下假设3是答案推一次。假设4是答案推一次。假设5是答案推一次。 保证三次都能退出循环