Easy难度第1题51Nod-2063 二分查找按二分查找的基本框架写就可以了直接上代码​ #includeiostream #includestring #includecstring using namespace std; int check(int arr[],int n,int k); int main() { int n,q, arr[100000]; cin n; for (int i 0; i n; i) { cin arr[i]; } cin q; int k; for (int i 0; i q; i) { cin k; if (check(arr, n, k)) { cout Yes endl; } else { cout No endl; } } return 0; } int check(int arr[], int n,int k) { int l, r, mid; l 0; r n - 1; while (l r) { mid (l r) / 2; if (arr[mid] k) return 1; else if (arr[mid] k) r mid - 1; else l mid 1; } return 0; } ​第2题洛谷-P1102 A-B 数对要找数对的个数由于我们给C赋值所以对于确定的B有确定的A值那么如何计算对于某个确定的B所对应的A数这是我们的主要问题这相当于在这串数中计算A值的个数一个个统计显然是低效的由于二分查找能够找到第一个和最后一个出现的要求值所以采用二分法那么对数串进行排序就必不可少了。​ ​ ​ #includeiostream #includestring #includecstring #includealgorithm using namespace std; void count(int arr[], int n, int c, int l, long long* p); int main() { int n, c; cin n c; int arr[200000]; for (int i 0; i n; i) { cin arr[i]; } sort(arr,arrn); long long num0; for (int i 0; i n; i) { count(arr, n, c, i, num); } cout num; return 0; } void count(int arr[],int n,int c,int l,long long *p) { int l1 l; int r n - 1; int mid; int num10, num20; while (l r) { mid (l r) / 2; if (arr[mid] c arr[l1]) { num2 mid; r mid - 1; } else if (arr[mid] c arr[l1])rmid-1; else l mid 1; } l l1; r n - 1; while (l r) { mid (l r) / 2; if (arr[mid] c arr[l1]) { num1 mid; l mid 1; } else if(arr[mid] c arr[l1])l mid 1; else r mid - 1; } (*p) (!num1?0:num1 - num2 1); } ​ ​Medium难度第3题洛谷-P8647 分巧克力二分答案的基本应用这题显然巧克力越大越难分且边长为整数故可用二分法设置最小可能值1和最大可能值1e5),利用二分法找到满足条件的最大值。它需要一个check判断函数显然的对于每个未切的长方形尽可能地从一角开始切不难得出每块长方形最多可切出(h[i]/x)*(w[i]/x)个正方形巧克力x是正方形边长h是长w是宽。最后统计判断切出的个数是否大于等于人数就行。#includeiostream #includestring #includecstring #includealgorithm using namespace std; int check(int h[], int w[], int n,int k,int x); int main() { int n, k; cin n k; int h[100000]; int w[100000]; for (int i 0; i n; i) { cin h[i] w[i]; } int r 10e5; int l 1; int mid; int ans; while (l r) { mid (r l) / 2; if (check(h,w,n,k,mid)) { ans mid; l mid 1; } else r mid - 1; } cout ans; return 0; } int check(int h[], int w[], int n, int k, int x) { int num 0; for (int i 0; i n; i) { num (h[i] / x) * (w[i] / x); } if (num k)return 1; return 0; }第4题洛谷-P8800 卡牌这题也是一样的越多套牌越难凑且整数套可用二分法。直接看check吧其实就是从牌1按顺序开始统计缺少的牌数要及时和可手写牌数进行比较以免做多余操作。要注意mn*n , n2e5 ,要long long#includeiostream #includestring #includecstring #includealgorithm using namespace std; int a[200000]; int b[200000]; int check(int a[], int b[], int n, long long m, int x); int main() { int n; long long m; cin n m; for (int i 0; i n; i) { cin a[i] ; } for (int i 0; i n; i) { cin b[i]; } int r 4e5; int l 0; int mid; int ans0; while (l r) { mid (r l) / 2; if (check(a, b, n, m, mid)) { ans mid; l mid 1; } else r mid - 1; } cout ans; return 0; } int check(int a[], int b[], int n, long long m, int x) { long long num 0; for (int i 0; i n; i) { if (x a[i] b[i])return 0; num ( x-a[i]0?x - a[i]:0); if (num m)return 0; } return 1; }Hard难度第5题洛谷-P1281 书的复制同上它也是符合二分法的条件的 这里提一下它的r,我起始给它了个所有页数总和。总体思路呢1.就是先找到满足条件的最大值2.然后根据这个最大值找出尽可能让前面的人少抄写的安排方法。对于第1步我们关注check,我们尽可能地从后往前题目要求滴都安排满由于每个人只能连着抄所以直接从后面开始让书尽可能组合在一起需要的人数如果符合就满足条件。对于第2步因为书是从后面开始分配的所以开了个数组记录了。详细操作看代码部分。#includeiostream #includestring #includecstring #includealgorithm using namespace std; int check(int arr[], int m, int k, int x); int main() { int m, k; cin m k; int k1 k; int arr[500]; int arr2[500][2]; long long num 0; for (int i 0; i m; i) { cin arr[i]; num arr[i]; } int l 1; long long r num; int mid; int ans0; while (l r) { mid (l r) / 2; if (check(arr,m,k,mid)) { ans mid; r mid - 1; } else { l mid 1; } } arr2[0][0] 1; int num2 0; for (int i m - 1; i 0; i--) { if (num2 arr[i] ans) { num2 0; arr2[k - 1][0] i2; i; k--; } else { num2 arr[i]; if (num2 arr[i]) { arr2[k - 1][1] i 1; } } } for (int i 0; i k1; i) { cout arr2[i][0] arr2[i][1] \n; } return 0; } int check(int arr[],int m,int k,int x) { int num 0; for (int i m - 1; i 0; i--) { if (x num)return 0; else{} if (num arr[i] x) { num arr[i]; k--; } else num arr[i]; } if (k 0)return 0; else return 1; }第6题洛谷-P8775 青蛙过河思路这题同样满足用二分的条件让我们将注意转到check,这个往返2*x趟其实可以等价于有2*x个小蛙蛙一起去上学我们要用跳跃能力y去判断是否可行那怎么判断呢用较小的数来具象化吧如y3时上图片没错每相邻三个站点高度和必须大于蛙蛙数 。同理每相邻y个站点的高度和必须大于蛙蛙数。#includeiostream using namespace std; int check(int s[], int n, int x, int y); int main() { int n, x; int h[100000]; int s[100000]; cin n x; for (int i 0; i n - 1; i) { cin h[i]; s[i] h[i] (i 0 ? 0 : s[i - 1]); } int l 1, r n; int mid 0; int ans 0; while (l r) { mid (l r) / 2; if (check(s, n - 1, 2*x, mid)) { ans mid; r mid - 1; } else { l mid 1; } } cout ans; return 0; } int check(int s[], int n, int x, int y) { if (y n) return 1; if (s[y - 1] x)return 0; for (int i y; i n; i) { if (s[i] - s[i - y] x)return 0; } return 1; }学习总结二分法基本套路框架二分答案在一些求最大值最小最小值最大正难则反的题的应用。其check是重点需要勤练和掌握更多知识。