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;
    }
};