大一寒假训练六（二分查找）【更新完成】

nefu 1648 小清新切绳子

【找最小值的最大值，judge函数有等于号】

二分查找最小值的最大值为ans，judge函数中return的时候要写等于号，
等于号在judge(m)中，则满足if(judge(m))时记下ans=m。

#include <bits/stdc++.h>
using namespace std;
int l,r,n,m,k,ans,a[10010];
bool judge(int m)
{
    int s=0;
    for(int i=1;i<=n;i++)
        s=s+a[i]/m;
    return s>=k;//有等于号
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>k)//分成k段
    {
        for(int i=1;i<=n;i++)
            cin>>a[i];
        l=0,r=10000000;
        while(l<=r)
        {
            m=l+(r-l)/2;
            if(judge(m))ans=m,l=m+1;//满足if(judge(m))，记下ans
            else r=m-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1211 卖古董-DP-二分

【找最大值的最小值，judge函数没有等于号】

二分查找最大值的最小值为ans，judge函数中return的时候没有等于号，
等于号不在judge(m)中，则不满足if(judge(m))时记下ans=m。

#include <bits/stdc++.h>
using namespace std;
int t,n,m,i,l,r,s,mid,cnt,sum,ans,tmpmax,a[100010];
bool  judge(int mid)
{
    s=0;cnt=1;
    for(i=1;i<=n;i++)
    {
        s=s+a[i];
        if(s>mid)
        {s=a[i];cnt++;}
    }
    return cnt>m;//没有等于号
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        tmpmax=sum=0;
        for(i=1;i<=n;i++)
        {cin>>a[i];tmpmax=max(tmpmax,a[i]);sum=sum+a[i];}
        l=tmpmax,r=sum;//这里必须要缩小初始区间为[tmpmax,sum]，如果写l=0,r=0x3f3f3f3f是错的
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(judge(mid))l=mid+1;
            else ans=mid,r=mid-1;//不满足if(judge(m))，记下ans
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1645 小清新的函数坐标

#include <bits/stdc++.h>
using namespace std;
double m,y;
double f(double x)
{return 0.0001*x*x*x*x*x+0.003*x*x*x+0.5*x-3;}
double seek(double l,double r,double cmp)
{
    while(r-l>1e-5)
    {
        m=l+(r-l)/2;
        if(f(m)>cmp) r=m;
        if(f(m)<cmp) l=m;
        if(f(m)==cmp) return m;
    }
    return m;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>y)
    printf("%.4lf\n",seek(-20,20,y));
    return 0;
}

nefu 956 二分查找
自己写的二分查找函数

//296ms
#include <bits/stdc++.h>
using namespace std;
int n,x,i,l,r,m,a[1000010];
int seek(int l,int r,int cmp)
{
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(a[m]>cmp)r=m-1;
        if(a[m]==cmp)return m+1;
        if(a[m]<cmp)l=m+1;
    }
    return r+1;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>x)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        printf("%d\n",seek(0,n-1,x));
    }
    return 0;
}

还可以用C++现成的函数！
C++其实有直接求出答案的函数：upper_bound，直接用这个函数比自己写的二分速度还快一些
upper_bound作用是返回数组a中第一个大于x的元素的下标ans，用法是ans=upper_bound(a,a+n,x)-a;

//136ms
#include <bits/stdc++.h>
using namespace std;
int n,x,i,a[1000010];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>x)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        printf("%d\n",upper_bound(a,a+n,x)-a);
    }
    return 0;
}

nefu 8 二倍的问题
数据小直接暴力枚举

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,t,n,ans,a[20];
    while(cin>>t)
    {
        while(t--)
        {
            n=ans=0;
            while(cin>>a[n]&&a[n])n++;//输入数据a[0]~a[n-1]
            sort(a,a+n);
            for(i=0;i<n;i++)
            {
                for(j=i+1;j<n;j++)
                {if(a[j]==a[i]*2)ans++;}
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

nefu 1647 小清新的二倍问题加强版-二分-桶排
上面那题的数据加强版，改进暴力枚举算法为二分查找算法。

//2532ms
#include <bits/stdc++.h>
using namespace std;
int n,i,l,r,m,cnt,ans,a[10010];
bool seek(int l,int r,int cmp)
{
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(a[m]>cmp)r=m-1;
        if(a[m]<cmp)l=m+1;
        if(a[m]==cmp)return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--)
    {
        ans=cnt=0;
        while(cin>>a[cnt]&&a[cnt])cnt++;
        sort(a,a+cnt);
        for(i=0;i<cnt;i++)
        ans=ans+seek(0,cnt-1,2*a[i]);
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1303 简单几何-二分
这题要特别注意精度：
1、π用acos(-1.0)表示
2、写原始式 h * ( p * r * r - r )，写成 h * r * ( p * r * - 1 ) 精度会错
3、实际上还要保留到8位小数而不是4位小数（题目的bug）

#include <bits/stdc++.h>
using namespace std;
const double p=acos(-1.0);//或者 #define p acos(-1.0)
int t,h;
double seek(double l,double r)
{
    double m=(l+r)/2.0;
    if(r-l<1e-8) return m;//题目要求输出保留4位小数，但是这里必须要写到8位小数的精度(题目的bug)
    if(pow(m,p)>=h*(p*m*m-m))return seek(l,m);
    //由于精度要求，必须写原始式h*(p*r*r-r)！写成h*r*(p*r*-1)精度会错！
    else return seek(m,r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>h;
        printf("%.4lf\n",seek(0,1e5));
    }
    return 0;
}

nefu 1646 小清新的二分查找之旅

#include <bits/stdc++.h>
using namespace std;
int n,q,k,i,l,r,m,a[1000010];
bool judge(int l,int r,int cmp)
{
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(a[m]>cmp) r=m-1;
        if(a[m]<cmp) l=m+1;
        if(a[m]==cmp) return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>q)
    {
        for(i=1;i<=n;i++)
        cin>>a[i];
        while(q--)
        {
            cin>>k;
            if(judge(1,n,k))printf("no\n");
            else printf("YES\n");
        }
    }
    return 0;
}