homework_2

发布于 2019-06-05  165 次阅读


二分算法是比较高效的算法,分为二分查找和二分答案

二分查找

在排好序的数组中查找所需元素的位置,单次查找复杂度(log2n)

思想就是比较自己的值和中间值的大小,比mid大就向右区间二分,比mid小就向左区间二分,直到自己的值和左端点的值相等。

二分答案

根据答案可以推出答案是否合理,一般题目关键字为最大值的最小或最小值的最大,每次判断二分的结果是否可以,如果可以存储并继续找更优的解,不可以就退一步找可以的解。

一本通1240

题目地址

玄学边界XD

#include<iostream>
#include<cmath>
#define N 1000010
#define int long long

int a[N];
int n,m,x,l,k,r,x1,x2,x3,x4,x5,y;

using namespace std;
signed main()
{
    cin>>n;
    a[0]=N;
    a[n+1]=N;
    a[n+2]=N;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    cin>>k;
    for (int i=1;i<=k;i++)
    {
        cin>>x;
        l=1;
        r=n;
        while (l<=r)
        {
            m=(l+r)/2;
            if (a[m]==x) break;
            if (a[m]>x) r=m-1;
            if (a[m]<x) l=m+1;
        }
        if (m==1) m++;
        x1=abs(a[m]-x),x2=abs(a[m-1]-x),x3=abs(x-a[m+1]),x4=abs(x-a[m+2]),x5=abs(x-a[m-2]);
        y=min(x1,min(x2,x3));
        if (y==x5) {cout<<a[m-2]<<endl;continue;}
        if (y==x2) {cout<<a[m-1]<<endl;continue;}
        if (y==x1) {cout<<a[m]<<endl;continue;}
        if (y==x3) {cout<<a[m+1]<<endl;continue;}
        if (y==x4) {cout<<a[m+2]<<endl;continue;}
    }
    return 0;
}

一本通1241

题目地址

提交答案题

#include<cstdio>
#include<iostream>

double pro(double x)
{
    return 1.0*x*x*x*x*x-15.0*x*x*x*x+85.0*x*x*x-225.0*x*x+274.0*x-121.0;
}

int main()
{
    double l=1.5, r=2.4,m;
    for(int i=1;i<=100;i++)
    {
        m=(l+r)/2.0;
        if (pro(m)==0)
        {
            printf("%0.6f",m);
            return 0;
        }
        if (pro(m)>0) l=m;
        else r=m;
    }
    printf("%0.6f",m);
    return 0;
}
/*
#include<iostream>
using namespace std;
int main()
{
    cout<<"1.849016"<<endl;
    return 0;
}
*/

洛谷P1577 切绳子

题目地址

#include<iostream>
#include<cstdio>
#include<cmath>
#define N 2000010
using namespace std;
int a[N],l=0,r=200000000,n,k,m;
int main()
{
    double f;
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>f;
        f*=100;
        a[i]=(int) f;
    }
    int cnt=0,ans=0;
    while (l<=r)
    {
        cnt=0;
        m=(l+r)/2;
        if (m==0) break;
        for (int i=1;i<=n;i++)
            cnt+=a[i]/m;
        if (cnt>=k) ans=max(ans,m),l=m+1;
        if (cnt<k) r=m-1;
        //if (cnt>k) l=m+1;
    }
    f=((double)ans)/100;
    printf("%0.2f",f);
    return 0;
}

洛谷P1284

题目地址

发现有一样的题,就不做CF那道了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110000
#define MAXN 1000000000
int a[N];
int n,c,ans=0;
bool pro(int x)
{
    int l=0,r=1,k=c;
    while (r<=n)
    {
        if (a[r]-a[l]>=x) k--,l=r;
        r++;
    }
    if (k<=0) return true;
    return false;
}
using namespace std;
int main()
{
    int l,r,m;
    cin>>n>>c;
    a[0]=-MAXN;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    l=1;
    r=MAXN;
    while (l<=r)
    {
        m=(l+r)>>1;
        if (pro(m)==true) ans=max(ans,m),l=m+1;
        else r=m-1;
    }
    cout<<ans<<endl;
    return 0;
}

最美好的事情就是和OI一起成长呢。