寒假训练专题一（二分、三分）

A

题目大意

题目先给出了一个算式，让你输入一个0~1e10的数y，找到在x范围为0~100内f（x）的最小值。

解题思路

因为当一个数达到级值的时候，f（x）'=0，而从原式可知，f（x）'是一个单调递增的函数，所以f（x）'<0时，x<x0,f(x)'>0时，x>x0,f（x）在x0处取得最小值。因此，可以用二分的方式查找，看他们的左右边界的中间值处f(x)'的大小，如果大于0，则这个中间值成为右边界，否则成为左边界，一直找到左边界与右边界的差值小于1e-5为止，此时得到的中间值即为x0。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-5;
int T;
double x,y,ans;
double ff(double a,double y)
{
    return 42*pow(a,6)+48*pow(a,5)+21*pow(a,2)+10*a-y;
}
double f(double mid,double y)
{
    return 6*pow(mid,7)+8*pow(mid,6)+7*pow(mid,3)+5*pow(mid,2)-y*mid;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf",&y);
        double l=0,r=100,mid;
        while(l+eps<=r)
        {
            mid=(l+r)/2;
            if(ff(mid,y)>0)
                r=mid;
            else
                l=mid;
        }
        printf("%.4lf\n",f(mid,y));
    }
    return 0;
}

B

题目大意

给你三个数组A、B、C，从这三个数组中，每个数组选出一个数字，问是否存在这样的三个数，使他们的和为x。

解题思路

题目其实就是问的能否找到三个数a，b，c，使a+b+c=x这个等式成立。如果用暴力三重循环，会超时。所以可以把这个等式改为a+b=x-c，先将a+b组成一个数组并排序，再用一个循环循环C这个数组里面的数得到x-c，再利用二分，二分a+b这个数组的坐标，如果得到的ab[mid]大于x-c，则右边界r=mid-1，如果小于，即左边界l=mid+1，否则就找到三个数使得a+b=x-c，返回1，找不到就返回0，最后根据返回的数输出YES 或者 NO。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e3+5;
int a[maxn],b[maxn],c[maxn],ab[maxn*maxn];
int num,L,M,N,S,x;
int fnd(int xx)
{
    int l=0,r=num-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(ab[mid]>xx)
            r=mid-1;
        else if(ab[mid]<xx)
            l=mid+1;
        else
            return 1;
    }
    return 0;
}
int main()
{
    int casee=0;
    while(~scanf("%d%d%d",&L,&N,&M))
    {
        num=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(int i=0; i<L; i++)
            scanf("%d",&a[i]);
        for(int i=0; i<N; i++)
            scanf("%d",&b[i]);
        for(int i=0; i<M; i++)
            scanf("%d",&c[i]);
        for(int i=0; i<L; i++)
            for(int j=0; j<N; j++)
                ab[num++]=a[i]+b[j];
        sort(ab,ab+num);
        scanf("%d",&S);
        printf("Case %d:\n",++casee);
        while(S--)
        {
            scanf("%d",&x);
            int tt=0;
            for(int i=0; i<M; i++)
            {
                int xx=x-c[i];
                if(fnd(xx))
                {
                    tt=1;
                    printf("YES\n");
                    break;
                }
            }
            if(!tt)
                printf("NO\n");
        }
    }
    return 0;
}

C

题目大意

给你两个数m和n，n表示一共会给你n天的预算，m表示要将这n天分成m份，然后给出这n天的预算，让你求出这m份中最小的最大值。

解题思路

要将n个数分为m份，求到最小的最大值，那么这个数最小就是这n个数的最大值，最大就是这n个数的和。因此，可以用二分的方式，令l为这n个数中的最大值，r为sum。每次将l和r的中间值带入进行计算，一共可以分成多少份，如果分的份数小于等于m，则表示我们需要的答案比这个mid小，则令r=mid-1，反之则表示答案比我们在mid下得到的份数大，则l=mid+1.直到l>r为止。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
long long a[maxn];
long long n,m;
long long Cnt(long long mm)
{
    long long sum=0,cnt=1;
    for(int i=0;i<n;i++)
    {
        sum+=a[i];
        if(sum>mm)
        {
            sum=a[i];
            cnt++;
        }
    }
    return cnt;
}
int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        memset(a,0,sizeof(a));
        long long sum=0,mx=-maxn-8;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            mx=max(mx,a[i]);
            sum+=a[i];
        }
        long long l=mx,r=sum,mid;
        while(l<=r)
        {
            mid=l+r>>1;
            long long k=Cnt(mid);
            if(k<=m)
                r=mid-1;
            else
                l=mid+1;
        }
        printf("%lld\n",mid);
    }
    return 0;
}

D

题目大意

给你三个数L，N，M。L表示起点到终点的距离，N表示一共有的石头的数量，M表示要去除的石头的数量，求去除这些石头之后，石头与石头之间以及石头与河岸之间最大的最小距离。

解题思路

先将两个河岸的距离标记，左端的河岸标记为l=0，右端的河岸标记为r=L。之后每次枚举一个距离mid=（l+r）/2，然后算出在该种距离下一共可以移除多少个石头，如果可移除的石头大于M，则表示这个距离太大，就令r=mid-1，否则就表示这个距离太小，则l=mid+1，直到l>r为止，因为是取得最大的最小距离，那么最终得到的l即为最大的最小距离。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=5e4+5;
int L,M,N;
int n[maxn];
int fnd(int l,int r,int k)
{
    int mark,cnt,mid;
    while(l<=r)
    {
        mark=0;
        cnt=0;
        mid=l+r>>1;
       // cout <<l<< " " << r << " " <<mid ;
        for(int i=1;i<=N+1;i++)
        {
            if(mid>=n[i]-n[mark])
                cnt++;
            else
                mark=i;
        }
        if(cnt>k)
            r=mid-1;
        else
            l=mid+1;
           // cout << " " << cnt << endl;
    }
    return l;
}
int main()
{
    cin>> L >> N >> M;
    for(int i=1;i<=N;i++)
        cin >> n[i];
    n[0]=0;
    n[N+1]=L;
    sort(n+1,n+N+1);
    printf("%d\n",fnd(0,L,M));
    return 0;
}

E

题目大意

某公司要建立一套通信系统，可以由n个厂家提供，每个厂家一共有m种设备，而每种设备有他们自己的带宽b和价格p，要求你从这n个厂家每个厂家挑选一种设备，使得得到的b/p值最大，其中这个b取所有设备中的最小值，p为所有设备的价格总和。

解题思路

可以从题目中得到一个递推公式dp[i][j]=min(dp[i][j],dp[i-1][k]+p),其中i为取到了第i家公司，j为取到这家公司的这个设备时，最小的带宽b，dp[i][j]的值为取到这个设备时的总价格p。最后取完所有的公司，再将所有的带宽跑一遍，取最大的b/p值。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std ;
const int INF=0x3f3f3f3f;
int t,n,m,b,p;
int dp[505][2005];
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i=0;i<=n;i++)
          for(int j=0;j<2005;j++)
            dp[i][j]=INF;
        for(int i=1;i<=n;i++)
        {
            cin >> m;
            for(int j=1;j<=m;j++)
            {
                cin >> b >> p;
                if(i==1)
                    dp[i][b]=p;
                else
                {
                    for(int k=0;k<1005;k++)
                    {
                        if(dp[i-1][k]!=INF)
                        {
                            if(b>k)
                                dp[i][k]=min(dp[i][k],dp[i-1][k]+p);
                            else
                                dp[i][b]=min(dp[i][b],dp[i-1][k]+p);
                        }
                    }
                }
            }
        }
        double ans=0,num;
        for(int i=0;i<2005;i++)
        {
            num=(double)i/dp[n][i];
            ans=max(ans,num);
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

F
题目大意

一个人在自己的家中，其中灯的高度为H，人的高度为h，房间总宽度为D，求人在他的家中的影子最长能有多长。

解题思路

从题目的图中可知，要求的影子的长为人在地板上的投影和在墙上的投影之和。而且可以知道如果人在灯下的话影子的长度为0，靠墙站时影子长度为h，而且明显可知影子最长的时候在这两个状态中间。因此，影子的长度是一个先增后减的过程。而从图中可以得到，如果我们设人在墙上的投影长为x，那么可以得到影子总的长度为(h-x)/(H-x)*D+x,(PS:不知道怎么来的看看高中数学。) 然后根据三分原理,可以算出答案。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const double esp=1e-4;
double H,h,D;
int T;
double f(double x)
{
    return (h-x)/(H-x)*D+x;
}
int main()
{
    double mid,mmid,l,r;
    cin >> T;
    while(T--)
    {
        cin >> H >> h >> D;
        l=0;
        r=h;
        while(r-l>esp)
        {
            mid=(l+r)/2;
            mmid=(mid+r)/2;
            if(f(mid)>f(mmid))
            {
                r=mmid;
            }
            else
                l=mid;
        }
        printf("%.3lf\n",f(l));
    }
    return 0;
}