1、枚举算法 1、枚举所有情况 2、判断每种情况是否符合条件 2、贪心算法 1、贪 排序 3、前缀和 定义: s[i]: 原数组 a 的前 i 个数(1 ~ i)的和 4、差分 定义: d[i]: 原数组 a 的相邻两项元素的差值 5、原 前 差的转换

二分查找 时间复杂度 O(logn) 前提: 数组是 有序的 1、二分模板 // 确定左右端点（二分范围） int l = 左端点,r = 右端点; int ans = 初始化; while(l<=r){ // 1、找中间值 int mid=(l+r)/2; // 2、比较查找到中间元素和目标元素的大小 if( ){ // 符合条件的情况 ans=mid; // 答案更新为 mid // 缩小范围 画图！判断缩小左边界还是右边界 // l=mid+1; r=mid-1; } else{ // 缩小范围 和上一个反过来 // r=mid-1; l=mid+1; } } 3、lower_bound 和 upper_bound

二分答案 1、确定单调性/二段性 二段性题目：找分界点 2、二分模板 int l=答案可能的最小值, r=答案可能的最大值; int ans=0; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=mid; // 求最大值 l=mid+1; // 求最小值 r=mid-1; } else{ // 求最大值 r=mid-1; // 求最小值 l=mid+1; } } 3、check 函数 具体问题具体分析 需要检查当前二分的答案是否符合题目要求 明确所有变量代表的意义 最后和什么比? 题目中的某一个定值 4、如何提升自己二分答案的能力