文章目录
- 二分模板
- 1460. 我在哪？
- 102. 最佳牛围栏
- 113. 特殊排序
二分模板
本文所使用的二分模板都是确保最终答案落在 [L,R] 以内，循环以 L==R 结束，每次二分的中间值会使mid成为左右区间的二者之一。
- 单调递增序列找
大于等于x的最小的值：区间的划分[l,mid][mid+1,r]
while (l<r){
int mid=l+r>>1;
if (nums[mid]>=x){ //check()
r=mid;
}
else{
l=mid+1;
}
}
return nums[l];这种写法规定不会取到 r这个值。
- 单调递增序列找
小于等于x的最大的值：区间的划分[l,mid-1][mid,r]
while (l<r){
int mid=1+l+r>>1;
if (nums[mid]<=x){ //check()
l=mid;
}
else{
r=mid-1;
}
}
return nums[l];这种写法规定不会取到l这个值。
- 实数域的二分模板：保留k位小数，则while中的精度取
1e-(k+2)
while (r-l>1e-5){ //for (int i=0;i<100;i++)
int mid=l+r>>1;
if (check()){
r=mid;
}
else{
l=mid;
}
}1460. 我在哪？
题目要求：有一个字符序列，找出一个最小的K，使得能够满足在K个元素的范围内，能够找到一个最短的没有重复出现的子字符串。
示例：
ABCDABC最大的K=4，此时最大的没有重复出现的子字符是：
ABCD因为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。
#include <iostream>
#include <unordered_set>
#include <string>
#include <cstring>
using namespace std;
#define int long long
string s;
int n;
bool check(int mid){
//检查在s中长度为mid的所有子串是否是不重复的
unordered_set<string> st;
for (int i=0;i+mid-1<s.size();i++){
string cur=s.substr(i,mid);
if (st.count(cur)){
return false;//重复
}
st.insert(cur);
}
return true;
}
signed main(){
cin>>n;
cin>>s;
int l=1,r=100;
while (l<r){
int mid=l+r>>1;
//寻找最小值
if (check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l;
return 0;
}102. 最佳牛围栏
题目要求：给你一个范围F和一组整数序列，在此序列中找到长度不小于F的子序列，使得这个子序列的平均值尽可能的大，求出平均值最大是多少。
示例：
F: 3
1 2 3 4 5 6结果为 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，寻找合法值。
(1 + 2 + 3) /3 = 2 ，即平均值是2
考虑让每个数字减去平均值: n1-avg + n2-avg + n3-avg 判断它的正负情况
1-1 + 2-1 + 3-1 = 3 //avg=1，合法，继续寻找最大的avg
1-2 + 2-2 + 3-2 = 0 //avg=0，合法，继续寻找最大的avg
-----
1-3 + 2-3 + 3-3 = -3 // avg=3，不合法了，需要缩小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的值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,F;
int nums[N];
double sum[N];
bool check(double avg){
//至少包含F个数的最大平均值
for (int i=1;i<=n;i++){
sum[i]=sum[i-1]+nums[i]-avg;//每个数字减去平均值
}
double minV=0;
for (int i=0,j=F;j<=n;j++,i++){//j至少等于F个数量
minV=min(minV,sum[i]);//找到前i个前缀和的最小值
if (sum[j]-minV>=0){
return true;//合法 存在sum[j]-sum[i]>=0 则存在以此avg作为平均值的包含K个数字的情况
}
}
return false;
}
int main(){
cin>>n>>F;
for (int i=1;i<=n;i++){
cin>>nums[i];
}
double l=1,r=2000;
while (r-l>1e-6){
double mid=(l+r)/2;
//枚举平均值的最大值
if (check(mid)){
l=mid;//找到最大值
}
else{
r=mid;
}
}
cout<<int(r*1000);
return 0;
}113. 特殊排序
题目要求：compare函数可以判断两个数字的大小关系，请把N个元素按照从小到大的顺序排序。
示例：
[[0, 1, 0],
[0, 0, 0],
[1, 1, 0]]元素大小的关系是N个点与他们的边构成的有向图。
因此这是一个了邻接矩阵，对角线的元素都是0，上下的关系是对称的，因此只需要看对角线上面即可。
（1，2）=1 表示1<2
（1，3）=0 表示1>3
（2，3）=0 表示2>3
因此排序如下：
3 1 2只需要按照从小到大排序即可，因此可以不用管第一个元素与最后一个元素。
由于我们需要按照从小到大排序，因此需要如果需要插入一个元素，则需要把这个元素插入到最后一个小于它的元素的后面。
仔细理解这句话，如果序列是：
2 4 5 7 ，现在要插入6我们暂时把元素大小看作是排序的规则。
因此我们选则把6插入到合适的位置loc，则loc=3（下标从1开始）。
即我们要插入到5的后面，这样才满足从小到大的排序：
2 4 5 [6] 7因此这道题就变成了从小于等于x的数中寻找最大值的问题，这不就是我们的第二套二分模板吗？
寻找小于等于x的最大值的问题：
while (l<r){
int mid=l+r+1>>1;
if (check()){
l=mid;
}
else{
r=mid-1;
}
}则找到的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就到达了第一个位置。
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> vec;
vec.push_back(1);
for (int i=2;i<=N;i++){
int l=0,r=vec.size()-1;
while (l<r){
int mid=(1+l+r)>>1;
//找到小于等于i的最大的那个位置
if (compare(vec[mid],i)){//如果vec[mid]<i
l=mid;
}
else{//vec[i]>=i
r=mid-1;
}
}
//r为合适的插入位置
vec.push_back(i);//先放进去，然后再交换位置
for (int j=(int)vec.size()-2;j>r;j--){
swap(vec[j],vec[j+1]);
}
if (compare(i,vec[r])){//比r还小，则放入第一个
swap(vec[r],vec[r+1]);
}
}
return vec;
}
};