type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
二分模板
本文所使用的二分模板都是确保最终答案落在 [L,R] 以内，循环以 L==R 结束，每次二分的中间值会使mid成为左右区间的二者之一。
- 单调递增序列找
大于等于x的最小的值：区间的划分[l,mid][mid+1,r]
这种写法规定不会取到
r这个值。- 单调递增序列找
小于等于x的最大的值：区间的划分[l,mid-1][mid,r]
这种写法规定不会取到
l这个值。- 实数域的二分模板：保留k位小数，则while中的精度取
1e-(k+2)
1460. 我在哪？
题目要求：有一个字符序列，找出一个最小的K，使得能够满足在K个元素的范围内，能够找到一个最短的没有重复出现的子字符串。
示例：
最大的K=4，此时最大的没有重复出现的子字符是：
因为ABC出现了两次，ABCDA虽然也是一次，但是不是最短的。
因此满足条件的：最短的字符串与最小的K 就是K=4的时候的
由于我们要求得使得满足K个范围内的最短的没有重复的子串，此时的K是多少。
即我们要取一个最小的可能的K，那么我们就可以利用第一种模板，
l=mid+1和R=mid来二分找到这个最小的K。我们二分枚举这个K，找到满足条件的最小的K即可。
因为我们要寻找的是最小值，所以套用这个模板；反之求最大值，则我们需要套用第二套模板。
那么我们的具体的check函数该如何写呢？
由于我们需要查找满足mid长度的子字符串不能有重复的，因此可以利用
字符串哈希或者set来判断重复元素即可。- 如果有每次截取一段字符串，判断是否跟之前重复，则返回false，此时我们修改
l=mid+1，表示当前的K太小了，存在重复出现的字符串，因此扩大左边界，寻找第一个满足条件的值。
- 如果没有重复，返回true，此时扩大缩小右边界
r=mid，寻找一个尽量小的值，因为我们要求的就是一个最小的满足条件的K。
- 最后while循环结束求出的就是最小的K。
102. 最佳牛围栏
题目要求：给你一个范围F和一组整数序列，在此序列中找到长度不小于F的子序列，使得这个子序列的平均值尽可能的大，求出平均值最大是多少。
示例：
结果为 4 5 6，最大的平均值是5，并输出平均值*1000后的值：5000
老规矩：平均值最大，很容易得知这是一个二分的题目，并且综合平均值可以是一个浮点数，因此该题是实数型的分二分查，套用实数型二分模板即可。
我们还需要规定一个精度：由于其每个数字的最大数量不会超过2000，因此我们可以考虑保留小数点后三位，设置
while (r-l>1e-5)即可，进行r=mid和l=mid的更新check函数如何写呢？
观察到一个性质：
- (num1+num2+num3)/3 =avg，即 num1+num2+num3=3*avg
- num1-avg + num2-avg + num3-avg =0，此时满足 num1+num2+num3=3*avg。
当2式的值等于0的时候，两者是等价的。
因此可以得知：
- 枚举n个数字的平均值avg，让每一个数字减去平均值avg，如果存在结果大于等于0，则是合法的，则需要扩大avg，寻找avg的最大值。
- 如果结果小于零，则以avg作为平均值是不合法的，需要缩小avg，寻找合法值。
到最后，avg只能取得2，因此就通过二分找到了三个数字的平均值。
我们把三个数字扩大到大于等于F个数字，并且在n个数字的序列中利用上面的方法寻找。
需要注意：逐个数字的操作太慢了，我们可以
前缀和进行优化。其中
sum[j]：记录了大于等于F个数字的子序列以 j 结尾的前缀和。
sum[i]：记录了大于等于F个数字的前面的部分，即
[0,n-F]的位置的前缀和，进行枚举 i 的位置。因为我们的子序列是大于等于F长度的，因此寻找在F序列的前面寻找一个最小的前缀和，只需使得 sum[j] - sum[i]>=0 即可，也就是sum[j] >= sum[i]成立，就是合法的avg，然后继续寻找更优的avg通过l与r的变化得到最优的avg的值。
113. 特殊排序
题目要求：compare函数可以判断两个数字的大小关系，请把N个元素按照从小到大的顺序排序。
示例：
元素大小的关系是N个点与他们的边构成的有向图。
因此这是一个了邻接矩阵，对角线的元素都是0，上下的关系是对称的，因此只需要看对角线上面即可。
（1，2）=1 表示1<2
（1，3）=0 表示1>3
（2，3）=0 表示2>3
因此排序如下：
只需要按照从小到大排序即可，因此可以不用管第一个元素与最后一个元素。
由于我们需要按照从小到大排序，因此需要如果需要插入一个元素，则需要把这个元素插入到最后一个小于它的元素的后面。
仔细理解这句话，如果序列是：
我们暂时把元素大小看作是排序的规则。
因此我们选则把6插入到合适的位置loc，则loc=3（下标从1开始）。
即我们要插入到5的后面，这样才满足从小到大的排序：
因此这道题就变成了从
小于等于x的数中寻找最大值的问题，这不就是我们的第二套二分模板吗？寻找小于等于x的最大值的问题：
则找到的
r就是我们的合适插入位置，即小于等于待插入的值得最大值，我们插入在它得后面。按照以下步骤：规定num为待插入的值
- 首先直接把num插入到末尾。
- 然后 j 从倒数第二个元素开始逆序遍历，执行当前位置与后一个位置的元素互换，则意味着把这个num往前移动（因为移动的都是目前compare大于num的），所以直到r的位置，num不在移动，则num就插入到了r位置的紧靠着的右边，同时num在移动的过程中后面比num大的也都在num的后面。
- 最后如果所有的元素都比num大，则num应该在首元素，此时r=0，我们经过了上面的移动，把
[1,res.size()-1]的元素都与num进行了交换，则num到达了第二个位置（下标1），则最后再与num[0]进行交换，则num就到达了第一个位置。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/c4f04c45-7cb8-480b-9877-411e33604d68
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。