复健\(Day2\)

今天复习二分，使用这种方法的比较明显的提示是使最大值最小，最小值最大，并且原序列有序或者说可以忽略次序

二分的基本模板

https://www.acwing.com/blog/content/2112/

题目

\(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\)