复健\(Day2\)
今天复习二分，使用这种方法的比较明显的提示是使最大值最小，最小值最大，并且原序列有序或者说可以忽略次序
二分的基本模板
\(1.\)闭区间写法
int binary_search(int l,int r,int target)//返回使check值大于等于target的最小的i(也就是l)
{//l=0,r=len(nums)-1
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)<target) l=mid+1;//[mid+1,r]
else r=mid-1;//[l,mid-1]
}
return l;//也可以是r+1
}
\(2.\)左闭右开区间
int binary_search(int l,int r,int target)
{//l=0,r=len(nums)
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)<target) l=mid+1;//[mid+1,r)
else r=mid;//[l,mid)
}
return l;//也可以是r
}
对于左开右闭区间那么就是\(l\)初始为\(-1,r\)初始为\(len(nums)-1,l=mid,r=mid-1\)
\(3.\)开区间
int binary_searck(int l,int r,int target)
{//l=-1,r=len(nums)
while(l+1<r)
{
int mid=(l+r)>>1;
if(check(mid)<target) l=mid;(mid,r)
else r=mid;//(l,mid)
}
return r;
}
题目
\(1.Acwing102\)
https://www.acwing.com/problem/content/104/
向下取整函数\(floor\)，\(double\) \(floor\)\((double\) \(arg)\)，向上取整函数\(ceil\)，用法与\(floor\)相同
#include<iostream>
#include<cstdio>
#include<cmath>
#define EPS 1e-5
#define maxn 100010
using namespace std;
int n,F;
int s[maxn];
double sum[maxn];
int Min(int a,int b)
{
return a>b?b:a;
}
int Max(int a,int b)
{
return a>b?a:b;
}
bool check(double ans)//双指针做法
{
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+s[i]-ans;
}
double minv=0;
for(int i=0,j=F;j<=n;i++,j++)
{
minv=min(minv,sum[i]);
if(sum[j]-minv>=0) return true;
}
return false;
}
int main()
{
cin>>n>>F;
double l=2000.0,r=1.0;
for(int i=1;i<=n;i++)
{
cin>>s[i];
l=Min(l,s[i]);
r=Max(r,s[i]);
}
while(r-l>EPS)
{
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d\n",int(r*1000));
return 0;
}
这道题要求我们找到一段长度大于等于\(F\)的区间，这段区间里牛的平均数要使得其最大
首先我们可以考虑到采用二重循环，枚举区间长度（大于等于F）以及起点，这样的时间复杂度是略小于\(O(n\ ^2)\)（在前缀和预处理的情况下）
我们思考要如何优化，在前缀和上考虑进行处理。平均数有一个很明显的性质，某个数减去平均数如果大于\(0\)，那么它本身就是大于平均数的，若小于\(0\)就是小于平均数的。因此我们用\(sum[i]\)记录\(s[1]-avg+s[2]-avg+s[3]-avg+...+s[i]-avg\)。
然后我们用两个指针\(i\)和\(j\)，我们初始化\(i=0,j=F\)，然后每次循环都\(i++,j++\)这样我们就可以保证\(i\)和\(j\)之间的距离始终保持为\(F\).
\(sum[j]-sum[i]\geqslant0\)时显然这一段的数减去平均大于等于\(0\)，也即满足平均值大于等与该二分的答案，这样是考虑了长度为\(F\)的区间，而对于大于\(F\)的区间，我们又用一个\(minv\)记录从\(1\)至\(i\)的过程中\(sum[i]\)的最小值，这是最优的一个最小值，当我们\(sum[j]-minv\geqslant0\)时，那么我们的平均值就满足条件了并且保证了区间长度大于等于\(F\)了
这样\(check\)函数就优化成了\(O(n)\)的复杂度了
\(Acwing113\)
https://www.acwing.com/problem/content/115/
关于交互式问题
// 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> v;
v.push_back(1);//将1装入v中，便于比较
for(int i=2;i<=N;i++)
{
int l=0,r=v.size()-1;
while(l<r)//找到第一个小于i的位置r
{
int mid=(l+r+1)>>1;//这里注意是l+r+1>>1
if(compare(v[mid],i)) l=mid;//v[mid]<i
else r=mid-1;
}
v.push_back(i);//把i放在v的最后一个位置
for(int j=v.size()-2;j>r;j--)//将i放在r+1的位置，然后把原本在r+1以及以后的数都往后移一位
{
swap(v[j],v[j+1]);
}
if(compare(i,v[r])) swap(v[r],v[r+1]);//i可能是最小的元素，v[r]仍然大于i，故这个时候我们做一个特殊判断
}
return v;
}
};
注意到我们这里的二分部分给的边界条件是\(l<r\)，然后\(mid\)的计算式\((l+r+1)>>1\)