CQUPT 集训队专题训练（二分/三分）

（二分/三分）

A - Strange fuction
题意：

F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) 
求x取（0，100）时，F(x)的最小值。

解题思路：

先将F(x)进行求导，然后求导之后的函数值为0时，此时用二分查找方法求出x,F(x)取值最小。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
double minn(double x,double y)
{
    double ans=6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
    return ans;
}
double solve(double x,double y)
{
    double ans=42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y;
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        double m;
        cin>>m;
        double x=0;
        double y=100.0;
        double mid;
        while(y-x>1e-5)
        {
            mid=(x+y)/2.0;
            if(solve(mid,m)>0)
            y=mid;
            else
            x=mid;
        }
        printf("%.4lf\n",minn(mid,m));
    }
    return 0;
}

B - Can you find it?
题意：

给出长度为L, N, M的序列a,b,c,(1<=L, N, M<=500),给出s个x，（1<=S<=1000），使得存在ai+bj+ck==x;

题解：

先枚举出ai+bj的所有值，（L*M），然后对于输出的每一个x,访问c的过程二分查找a+b的和，判断是否等于x。查找过程的复杂度为o(s*m*log(l*n))

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long ll[600],nn[600],mm[600],ln[300008];
int main()
{
    long long l,n,m,s,x;
    int cas=1;
    while(scanf("%lld%lld%lld",&l,&n,&m)!=EOF)
    {
        for(int i=0;i<l;i++)
        scanf("%lld",&ll[i]);
        for(int i=0;i<n;i++)
        scanf("%lld",&nn[i]);
        for(int i=0;i<m;i++)
        scanf("%lld",&mm[i]);
        scanf("%lld",&s);
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<n;j++)
            ln[i*n+j]=ll[i]+nn[j];
        }
        sort(ln,ln+l*n);
        sort(mm,mm+m);
        cout<<"Case "<<cas++<<":"<<endl;
        for(int k=0;k<s;k++)
        {
            scanf("%lld",&x);
            if((ln[0]+mm[0])>x||(ln[l*n-1]+mm[m-1])<x)
            cout<<"NO"<<endl;
            else
            {
                long long r=l*n-1,le=0;
                int flag=0;
                for(int i=0;i<m;i++)
                {
                    while(le<=r)
                    {
                        long long mid=(le+r)/2;
                        if(mm[i]+ln[mid]==x)
                        {
                            flag=1;
                            break;
                        }else if(mm[i]+ln[mid]>x)
                        {
                            r=mid-1;
                        }else
                        {
                            le=mid+1;
                        }
                    }
                   le=0;
                   r=l*n-1;
                   if(flag)break;
                }
                if(flag)
                    cout<<"YES"<<endl;
                else
                    cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}

C - Monthly Expense
最大值最小值问题
题意：

将N天 (1 ≤ N ≤ 100,000)划分为M (1 ≤ M ≤ N) 段，每一段为这一段天数花费的总和，问预算最多的那一段最少为多少？

解题思路：

利用二分的方法将假设预算，如果pi<预算，就将pi加到这一段，否则就加到下一段。若pi>预算或者num>M,表示不满足条件。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m;
int a[100086];
int sol(long long x)
{
    long long sum=0;
    int num=1;
    for(int i=0;i<n;i++)
    {
        if(sum+a[i]<=x)
        {
            sum+=a[i];
        }else
        {
            num++;
            sum=a[i];
        }
        if(num>m||x<a[i])
        return 0;
    }
    return 1;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        long long sum=0,maxn=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(a[i]>maxn)
            maxn=a[i];
        }
        long long l=maxn,r=sum;
        long long mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(sol(mid))
            {
                r=mid-1;
            }else
            l=mid+1;
        }
        cout<<mid<<endl;
    }
    return 0;
}

D - River Hopscotch
最小值最大值问题
题意：

长度为L(1 ≤ L ≤ 1,000,000,000)的河流之间有N(0 ≤ N ≤50,000)块石头，可以踩石头过河，Di为从开始到第i块石头的距离，求搬走 M(0 ≤ M ≤ N) 块石头后，两块石头最大距离的最小距离是多少

解题思路：

将所要求的值进行由二分求得，此值定在（0，L），求得此值后进行判断搬走的石头mm>m时，说明mid此值太大

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int d[60000];
int n,l,m;
int sol(int mid)
{
    int mm=0,j=0;
    int temp=0;
    for(int i=1;i<=n+1;i++)
    {
        temp+=d[i]-d[i-1];
        if(temp<mid)
        mm++;
        else
        temp=0;
        if(mm>m)
        {
            return 1;
            break;
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d%d",&l,&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
        d[0]=0;
        d[n+1]=l;
        sort(d,d+n+2);
        int lef=1,ri=l;
        int mid;
        while(lef<=ri)
        {
            mid=(lef+ri)/2;
            if(sol(mid))
            {
                ri=mid-1;
            }else
            lef=mid+1;
        }
        cout<<lef-1<<endl;
    }
    return 0;
}

E - Communication System
比值最大值
题意：

有n (1 ≤ n ≤ 100)种设备，每一种设备有mi种选择，每一个设备有B带宽和价格P，从每一种设备中选择一个求所选中最小带宽比总的价格的最大值。（B/P）

解题思路：

暴力枚举出所有带宽（此带宽定在最小带宽和最大带宽之间），再枚举出不同种类所有大于等于此带宽K的最小价格，有贪心可得，B/（价格P和的最小值）得出比值最大。（同样也可以用三分求凸函数的最大值）

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int ba[105][105],pri[105][105];
int m[105];
int low,hign;
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        low=0xffff;
        hign=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&m[i]);
            for(int j=1;j<=m[i];j++)
            {
                scanf("%d%d",&ba[i][j],&pri[i][j]);
                if(ba[i][j]<low)
                low=ba[i][j];
                if(ba[i][j]>hign)
                hign=ba[i][j];
            }
        }
        double bili=0;
            for(int k=low;k<=hign;k++)
            {
                int sump=0;
                for(int i=1;i<=n;i++)
                {
                    int minp=0xffff;
                    for(int j=1;j<=m[i];j++)
                    {
                        if(ba[i][j]>=k&&pri[i][j]<minp)
                        minp=pri[i][j];
                    }
                    sump+=minp;
                }
                if(k*1.0/sump>bili)
                bili=k*1.0/sump;
            }
        printf("%.3f\n",bili);
    }
    return 0;
}

F - Light Bulb
三分
题意：

站在灯下的高度h（0.01，1000）人，可以左右移动，在距离灯为D（0.01，1000）的位置为墙壁，H（0.01，1000）为灯的高度，并且H - h >= 0.01，求此人影子最长为多少

解题思路：

求凸函数的最大值，有题意可知此人在（0，D）之间移动，当移动到某一位置时，影子的长度达到最大。
1影子未达到墙壁并在地面上移动，不能达到最长，
2当此人影子当好碰到墙壁时，所在的位置是(H-h)*D/H，最大值所在范围（(H-h)*D/H，D），
3影子映射到墙壁上，求出函数D-x+H-(H-h)*D/x为影子长度。

代码：

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