lower_bound与upper_bound
整数集合上的二分
1.最佳牛围栏
原题链接
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int cow[N];
double sum[N];
int n,m;
bool check(double avg)
{
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+cow[i]-avg; //先求一下前缀和
double minv=0;
for(int i=0,j=m;j<=n;i++,j++)
{
minv=min(minv,sum[i]);
if(sum[j]>=minv)
return true;
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>cow[i];
double l=0,r=2000;
while(r-l>1e-5)
{
double mid=(r+l)/2;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%d\n",int(r*1000));
return 0;
}
2.特殊排序
原题链接
根据数学归纳法，假设前k-1个元素已经按要求排成一行，如果能确定第k个元素应该放在哪一个前面，即可解决此问题。
可以证明二分一定可以找到一个合法的位置插入，证明如下：
- 1.如果第k个元素比第mid个元素小。
继续比较k与mid-1这两个元素，若第k个元素比第mid-1个元素大，则k可以插在mid-1与mid之间；否则说明元素k比元素mid-1小，那就再比较k与mid-2这两个元素，依此类推，直到发现第k个元素比第1个元素小，那就放在最前面
// 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>res;
res.push_back(1);
for(int i=2;i<=N;i++)
{
int l=-1,r=res.size()-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(compare(res[mid],i))
l=mid;
else
r=mid-1;
}
res.push_back(i);
//若i小于res中的所有数,那么i要扔到0处，那么r二分后的值得是-1
for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
}
return res;
}
};
