最佳牛围栏：二分+双指针+前缀和
问题抽象：给定n个数，选择连续的一段数，在选择的个数大于f的前提下，要求选中的数的平均值最大。
考虑绝对正确做法:枚举选择数的个数，枚举第一个数字的位置，利用前缀和快速求出总和，求出平均值，选择最大的平均值。
考虑时间复杂度：n个数，假设个数大于1，最坏情况下是O(n^2)。n为10的五次方，会tml。（只能通过11个数据）
猜测：O(nlogn)的时间复杂度是可以接受的，考虑二分答案。接着发现给定一个平均数，平均数对其中的每个数相减，再求前缀和，如果和大于等于0，说明该平均数比该段区间的平均数大于或者相等。在接着寻找有没有俩段的区间和大于等于0，并且这个区间长度大于f，如果有，则该平均数可以，并且偏小或者等于最终答案。
对于查找有没有俩段的区间和大于等于0，并且这个区间长度大于f，利用双指针进行最小前缀最大后缀优化。
感受：这题谁能想出来。。。。
借教室：二分+差分
题目抽象：有n个数，和m个操作，每个操作会对一段区间进行减值，要求判断是否会有值小于0，如果有，是那次操作。（操作按顺序来）
绝对正确做法：枚举操作，每次枚举进行减值（利用差分，也要求前缀和的），在减值的同时对每个数进行判断，是否小于0，如果有，则输出-1，输出操作编号，return，如果到最后都没有，输出0。
考虑时间复杂度：O(n*m)，n和m最大为1e6。会tml。
考虑适合的时间复杂度：O(nlogm) , O(mlogn)，一般是二分。
考虑优化：假设二分寻找操作，对于每堆操作，通过差分+前缀和快速实现区间修改，再求前缀和的同时即可顺带判断是否会小于0，（这里不必加上原数组，可以直接进行差分，最后判断的时候加上原数组判断即可。也就是前缀和与原数组无关）
如果小于0，说明到目前这个操作，是不行，答案一定是它或者它前面的，r=mid。
如果没有小于0的，说明到目前这个操作，都是不会有问题的，l=mid，答案一定在这次后面。答案拥有二段性。
考虑时间复杂度：枚举操作为O(logm),每次有O(logm+n)，logm为通过操作数进行差分，n为求前缀和并且判断。
总的时间复杂度为
O(2logm + n*logm)=O(logm(2+n))=O(nlogm)
1227. 分巧克力：二分
题目抽象：有n个长方形，要求将长方形至少切割出k个一样的正方形，求正方形边长的最大值。
绝对正确的做法：枚举正方形的边长，对每个长方形进行切割，将能切的总数加起来，判断是否超过k个，如果超过，更新答案，如果没有就不更新。
考虑时间复杂度：n最大为1e5，长方形边长m最大为1e5，所以需要枚举的正方形边长也为m。总为O(n*m)。会tml
考虑适合的时间复杂度：O(mlogn),O(nlogm)，二分最合适
考虑优化：尝试二分，发现二分n个长方形没有意义，接着尝试二分正方形边长。对于一个正方形边长，可以轻易知道某个长方形能划分多少个正方形边长，将所有的数量相加，如果大于k个，答案符合要求，观察发现，如果小于这个边长的正方形，一定都能够被划分出至少k个正方形。而大于该边长，不一定能划分出来，由于寻找最大值，最大值一定在当前的这个边长，或者比该边长大的边长之中。答案具有二段性。
考虑时间复杂度：正方形边长的二分是O(logm)，m为长方形边长的最大值。每次二分，都需要遍历n个长方形，记录答案数量。所以总的时间复杂度为O(n*logm)。
5407. 管道：二分+区间合并+差分
题目抽象：有len个数，其中有n个数拥有值s，l。
对于某个数t，会从1开始，如果t大于当前s，那么会将l-(t-s)和l+(t-s)范围的数标记，否则会一直自加，直到大于s，并将l-(t-s)和l+(t-s)范围的数标记。要求最小的t使得全部数被标记。
绝对正确的做法：从小到大枚举t，判断是否可以将所有数标记。
考虑时间复杂度：如果仅抽象考虑，t最大为len的最大值，再考虑开始的时间拉满，开始的阀门不开，不会流水，为len的2倍，也就是2e9。判断数时，需要枚举n,为1e5。
O(2len*n)=O(2e14) tml到姥姥家了。
考虑适合的时间复杂度：如果len为倍数，一定不行，考虑将len变为log。那么可能就是O(n*log(len))。
考虑优化：从二分来讲就是二分len，而len的时间复杂度是服务t的，所以本质上就是二分t。每次对于一个水流来的时间，可以算出能够标记的点，这个时间复杂度是O(n)。接着我们还需要判断所有的点是否都被标记，如果暴力的判断，还是要枚举n，进行修改，O(n^2)的时间复杂度。
总的时间复杂度为O(n^2log(len)+nlog(len)),由于存在O(n^2)，n最大为1e5，肯定是不行的。
考虑优化判断操作：我们知道哪段区间被标记了，因此对哪段区间进行排序，然后可以枚举区间，进行区间合并操作，也就是通过俩个指针，如果该区间的左端点大于右指针，说明这个区间不包含在指针内。如果该区间的左端点小于右指针，说明包括在内，可以合并，合并就是将右端点和右指针取max。而上一种无法合并的情况，我们只能考虑新的区间是否能合并接下来的一些区间，所以让我们的左右指针都进行更新，更新为新区间。
对区间不包含在指针内的操作，也就是更新俩个指针，是有效的证明：
假设存在某个区间在当前遍历区间之后，可以包含当前遍历的区间和左右指针，那么该区间的左端点一定小于等于左指针和当前遍历区间的左端点。假设是小于，那么该区间一定会先被遍历到，与假设矛盾。假设是等于，那么该区间被后遍历到不会影响有效性。因为该区间的左端点小于右指针，那么就是可以合并的情况。
4956. 冶炼金属：二分+整除
题目抽象：n对数，表示a除以某个数t得到了b。求t的最小值和最大值。
绝对正确：枚举t，再枚举n，查看是否满足要求，第一个满足的就是最小，最后一个满足的就是最大。
时间复杂度：a和b最大值是1e9，O(nt)的时间复杂度肯定不行。
尝试适合的时间复杂度：O(nlogt)
尝试优化：二分t，对于每个t，只要枚举n，查看每个a除t是否为b，如果大于，说明t小了，应该增大t。如果小于，说明t大了，应该减少t。但是当等于的时候，由于需要求最小值和最大值，可以利用不同的check函数进行操作。
当球t的最小值时，如果a除t大于b了，说明t小了，答案不符合要求，如果小于，t大了。如果等于，t可能会大，答案一定在当前的t或者比t小的数中，可让r=mid，答案具有二段线。
当求t最大值时，如果t正好，答案一定在t或者大于t的值中。答案具有二段性。
考虑时间复杂度：O(2nlogt)
4656. 技能升级
题目抽象：n个等差数列，在选每个数必须选完上一个数时才能继续选(比如第一个等差数列，必须选完a1才能选a2)，求选m个数的最大值。
绝对正确的做法：组合问题，暴力枚举所有可能，求最大值。
不用想就超时
考虑优化：由于数字一定，最终答案是一定的，并且可知最后答案是由前大于等于t个数相加而得，由此可以二分t的位置，如果当前的前t个数小于等于m，说明前t个数比最大小。如果前t个数大于m，说明前t个数比最大值大，答案应该比其小。具有二段性。
而求个数，利用公式即可快速求出。
最终答案需要减去多余的部分，因为结果为t的值可能有很多。
4176. 愤怒的牛
题目抽象：从n个数中选出m个数，要求这m个数之间的最大的差值最小为多少。
绝对正确：枚举n个数，枚举m个数。O(n*m)
二分：二分这个差值最小，利用贪心思想，每次遍历到的这个数一旦比上一个数大于等于这个差值，就答案自加，最后比较答案是否大于等于m，如果是，说明答案符号要求，最小一定在大于等于这个数。答案具有二段性。
