寒假集训队训练题-二分+三分

A - Strange fuction

题目大意：给定公式和定义域，求函数极值

解题思路：标准三分法

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
#define MOD 1000000
using namespace std;
double cal(double y,double x)
{
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
void find_min(double y)
{
    double x,l=0,r=100,l_,r_;
    while(r-l>1e-6)
    {
        l_=l+(double)1/3*(r-l);
        r_=r-(double)1/3*(r-l);
        if(cal(y,l_)>cal(y,r_)) l=l_;
        else r=r_;
    }
    printf("%.4f\n",cal(y,r));
}
int main()
{
    int i,t;
    double y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf",&y);
        find_min(y);
    }
    return 0;
}

B - Can you find it?

题目大意：输入n组整数x，y，z，求多组数据是否满足xi+yj+zk是否等于给定数据，i，j，k代表组的下标。

解题思路：将x和y的任意组合都求出，用二分法查找是否在z中存在zk=m-xi-yj

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int A[501],B[501],C[501],S[1001],BC[250001];
int main()
{
    int i,j,k,x,t,flag=0,L,M,N,count_=0;
    while (scanf("%d%d%d",&L,&N,&M)==3)
    {
        for (i=0; i<L; i++)
            scanf("%d",&A[i]);
        for (i=0; i<N; i++)
            scanf("%d",&B[i]);
        for (i=0; i<M; i++)
            scanf("%d",&C[i]);
        scanf("%d",&t);
        for (i=0; i<t; i++)
            scanf("%d",&S[i]);
        for (j=0; j<N; j++)
            for (k=0; k<M; k++)
            {
                BC[j*N+k]=B[j]+C[k];
            }
        sort(BC,BC+M*N);
        printf("Case %d:\n",++count_);
        for(i=0; i<t; i++)
        {
            flag=0;
            for (j=0; j<L; j++)
            {
                x=S[i]-A[j];
                if(upper_bound(BC,BC+M*N,x)-lower_bound(BC,BC+M*N,x))
                {
                    printf("YES\n");
                    flag=1;
                    break;
                }
            }
            if (flag==0) printf("NO\n");
        }
    }
    return 0;
}

C - Monthly Expense

题目大意：给定n，m，要求将n个数划分为m组，且所有组的和的最大值应该是可能的划分方案中最小的

解题思路：在最大的数和所有数的总和范围内二分查找满足划分为m组的最小值

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int a[100000];
int N,M;
int cal(int mid)
{
    int i,count_=0,sum=0;
    for(i=0;i<N;i++)
    {
        sum+=a[i];
        if (sum>mid)
        {
            count_++;
            sum=a[i];
        }
    }
    count_++;
    return count_;
}
int main()
{
    int i,Max=-1,sum=0,lb,ub,mid;
    scanf("%d%d",&N,&M);
    for (i=0;i<N;i++)
        {
            scanf("%d",&a[i]);
            Max=max(a[i],Max);
            sum+=a[i];
        }
    lb=Max;
    ub=sum;
    while(ub-lb>=0)
    {
        mid=(lb+ub)/2;
        if (cal(mid)<=M) ub=mid-1;
        else lb=mid+1;
    }
    printf("%d\n",mid);
    return 0;
}

D - River Hopscotch

题目大意：给n个点，总距离为l，且已知每个点到起点的距离，要求删除m个点，且删除后每个点之间的距离的最小值是所有可能的删除方案中最大的

解题思路：在0到l+1范围内二分查找一个删除后的最短距离使得满足恰好删除m个点

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int d[50005];
int L,N,M;
int cal(int mid)
{
    int i,count_=0,t;
    for(i=0;i<=N;i++)
    {
        t=i;
        while (t<N+1 && d[i]+mid>d[t+1]) {count_++;t++;}
        i=t;
    }
    return count_;
}
int main()
{
    int i,ub,lb,mid;
    scanf("%d%d%d",&L,&N,&M);
    for (i=1;i<=N;i++)
        scanf("%d",&d[i]);
    d[0]=0;
    d[N+1]=L;
    sort(d,d+N+2);
    ub=L+1;
    lb=0;
    while (lb+1<ub)
    {
        mid=(lb+ub)/2;
        if (cal(mid)>M) ub=mid;
        else lb=mid;
        //printf("%d~%d\n",lb,ub);
    }
    printf("%d",lb);
    return 0;
}

E - Communication System

题目大意：给定n类要购买的材料，每一类有任意组供应商，每个供应商显示其材料的带宽和价格，每一类材料任选一个供应商，求所选供应商带宽的最小值除以价格总和的最大值

解题思路：先将所有带宽存储并排序，开始三分求最大值，对于每一个带宽，以它为最小带宽，在其他类材料里查找最小价格，得出此带宽的最大带宽除以总价

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int p[105][105],b[105][105],all[105*105],count_[105];
double cal(int x,int n)
{
    int i,j;
    double sum=0;
    for (i=0;i<n;i++)
    {
        int min_=1<<29;
        for (j=0;j<count_[i];j++)
        {
            if (b[i][j]>=all[x])
            {
                min_=min(min_,p[i][j]);
            }
        }
        sum+=min_;
    }
    return all[x]/sum;
}
int main()
{
    int t,n,m,i,j,num=0,l,r,l_,r_;
    scanf("%d",&t);
    while (t--)
    {
        num=0;
        scanf("%d",&n);
        for (i=0;i<n;i++)
        {
            scanf("%d",&m);
            count_[i]=m;
            for (j=0;j<m;j++)
                {
                    scanf("%d%d",&b[i][j],&p[i][j]);
                    all[num++]=b[i][j];
                }
        }
        sort(all,all+num);
        l=0;
        r=num-1;
        while (l+1<r)
        {
            l_=(l+r)/2;
            r_=(l_+r)/2;
            if (cal(l_,n)<cal(r_,n)) l=l_;
            else r=r_;
        }
        printf("%.3f\n",max(cal(l,n),cal(r,n)));
    }
    return 0;
}

F - Light Bulb

题目大意：给定实际问题，有一个房间，有灯，人和墙，求灯光投影的最大长度

解题思路：推导长度公式，确定定义域，使用三分法求极值

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
double H,h,d;
double cal(double x)
{
    double res;
    res=(H*H*x+h*(x+d)*(x+d))/(H*(x+d))-x;
    return res;
}
int main()
{
    int t;
    double l,r,l_,r_;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lf%lf%lf",&H,&h,&d);
        l=0;
        r=h*d/(H-h);
        while(r-l>1e-9)
        {
            l_=l+(r-l)/3;
            r_=r-(r-l)/3;
            if (cal(l_)<cal(r_)) l=l_;
            else r=r_;
        }
        printf("%.3f\n",cal(r));
    }
    return 0;
}