2016寒假集训队第一次作业

题解

Problem A:Strange fuction

题意：给定一个f(x)=6*x^7+8*x^6+7*x^3+5*x^2-y*x，求出它在x属于[0,100]的时候的最小值。

题解：综合题目大意和本次作业的主题。。很容易想到要用三分法求最值（二分法要求单调），于是。。这道题似乎就是一个裸的三分了。。。。(注意要保留4位小数而题目中没说哦～)

参考代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t;
double y,mid,mmid,l,r;
double getf(double x,double y)
{
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>y;
        l=0;
        r=100;
        for (int i=0; i<200; i++)
        {
            mid=(l+r)/2;
            mmid=(mid+r)/2;
            if (getf(mid,y)<getf(mmid,y)) r=mmid;
            else l=mid;
        }
        printf("%.4lf\n",getf(mid,y));
    }
    return 0;
}

Problem B:Can you find it?

题意：给定三个数列，长度分别为l,m,n,都属于0～500。现在要任意组合这三个数列中的数看相加能否为x，能输出yes，不能输出no，有1000个询问。

题解：一开始想的是直接三个数列依次相加，但是这样是500*500*500*1000，不用想肯定会爆炸。再加上这次的主题是二分，于是想到了一个算法：把一个数列拿去排序然后二分看能否等于x，但在t了几发之后发现好像500*500*log500*1000也会爆炸。。。然后想了一会儿发现自己傻逼了，既然可以一个拿来二分，那就可以预处理出三个数组中两个数组的和的值，放在一个新的数组里面然后就可以优化成500*log(500*500)*1000，这样就不会爆炸了（智商受限严重）。。。

参考代码：

#include<iostream>
#include<algorithm>
using namespace std;
int l,m,n,d=1,t,k;
long long x;
bool bo1,bo2;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>l>>m>>n)
    {
        long long a[505],b[505],c[505],p[250005];
        k=1;
        for(int i=1; i<=l; i++)
            cin>>a[i];
        for(int i=1; i<=m; i++)
            cin>>b[i];
        for(int i=1; i<=n; i++)
            cin>>c[i];
        for(int i=1; i<=l; i++)
            for(int j=1; j<=m; j++)
            {
                p[k]=a[i]+b[j];
                //cout<<p[k]<<" ";
                k++;
                //cout<<p[k]<<" ";
            }
        //cout<<endl;
        sort(p+1,p+k);
        //for (int i=1; i<=k-1; i++)
        //    cout<<p[k]<<" ";
        cin>>t;
        cout<<"Case "<<d++<<":"<<endl;
        while(t--)
        {
            cin>>x;
            bo1=false;
            bo2=false;
            for (int i=1; i<=n; i++)
            {
                int l=1,r=k-1;
                while (l<=r)
                {
                    int mid=(l+r)/2;
                    if (p[mid]+c[i]==x)
                    {
                        bo1=true;
                        bo2=true;
                        break;
                    }
                    else if (p[mid]+c[i]<x)
                    {
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                if (bo1) break;
            }
            if (bo1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }     
    }  
    return 0;  
}

Problem C: Monthly Expense

题意：已知农夫在n天中每天的花费，要求把这n天分作m组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值。

题解：二分答案，可知最小的可能就是a[i]中的最大值，而最大的可能是整个a数组的和，于是取到了l和r，二分答案检查是否满足刚好可以分为m组，如果大于m组说明偏小了，可以增大，反之可以减小。

参考代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,sum,t,a[100005],ans,l,r,mid;
bool judge(int ans)
{
    sum=0;
    t=1;
    for (int i=1; i<=n; i++)
    {
        if (sum+a[i]<=ans) sum+=a[i];
        else
        {
            sum=a[i];
            t++;
        }
    }
    if (t>m) return 0;
    else return 1;
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
        l=max(l,a[i]);
        r+=a[i];
    }
    while (l<=r)
    {
        mid=(l+r)/2;
        if (judge(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<mid<<endl;
    return 0;
}

Problem D:River Hopscotch

题意：有一条河长L，中间N块石头，最多去掉M块，求任意两个石头间最小距离的最大值.

题解：二分最小值，再比较最小值是mid时去掉的石头个数来改动l和r，题目的思路和C类似。值得注意的是有可能把所有石子全部取完。。所以在二分的初始时候要把r设置的大一些（wa了两发。。。）

参考代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int l,n,m,a[50005],t,k,l1,r,mid;
bool judge(int mid)
{
    t=0;
    k=0;
    int i=1;
    while (i<=n+1)
    {
        if (a[i]-a[k]>=mid)
        {
            i++;
            k=i-1;
        }
        else
        {
            i++;
            t++;
        }
    }
    if (t<=m) return 1;
    else return 0;
}
int main()
{
    cin>>l>>n>>m;
    a[0]=0;
    a[n+1]=l;
    for (int i=1; i<=n; i++)
        cin>>a[i];
    sort(a,a+n+1);
    l1=0;
    r=l+l;
    while (r-l1>1)
    {
        mid=(r+l1)/2;
        if (judge(mid)) l1=mid;
        else r=mid;
    }
    cout<<l1<<endl;
    return 0;
}

Problem E:Communication System

题意：有n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：B和P。每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。其中B为这n件设备的带宽的最小值，P为这n件设备的总价。

题解：额。。看了下数据范围。。发现好像只要枚举所有可能符合条件的B值也可以。。。就没有用二分来做。。。

参考代码：

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
struct note
{
    int b,p;
}a[105][105];
int n,num[105],maxx[105],minn[105],t,sum,s1,s2,mp;
double ans;
int find(int b)
{
    sum=0;
    for(int i=1; i<=n; i++)
    {
        mp=1000000000;
        for(int j=1; j<=num[i]; j++)
        {
            if (a[i][j].b>=b)
                mp=min(mp,a[i][j].p);
        }
        sum+=mp;
    }
    return sum;
}
int main()
{
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n;
        for (int i=1; i<=n; i++)
        {
            cin>>num[i];
            for(int j=1; j<=num[i]; j++)
                cin>>a[i][j].b>>a[i][j].p;
        }
        for(int i=1; i<=n; i++)
        {
            minn[i]=a[i][1].b;
            maxx[i]=a[i][1].b;
            for (int j=2; j<=num[i]; j++)
            {
                maxx[i]=max(maxx[i],a[i][j].b);
                minn[i]=min(minn[i],a[i][j].b);
            }
        }
        s1=minn[1];
        s2=maxx[1];
        for(int i=2; i<=n; i++)
        {
            s1=min(s1,minn[i]);
            s2=min(s2,maxx[i]);
        }
        for(int i=s1; i<=s2; i++)
            ans=max(ans,(double)i/(double)find(i));
        printf("%.3lf\n",ans);
    }
    return 0;
}

Problem F:Light Bulb

题意：求人从左向右走动时，影子的长度L的最大值。

题解：感觉是一道数学题。。因为明显从灯下开始往右走影子先会慢慢变长，但是到了某一点影子开始投射在墙上，于是又会慢慢变短。因此这个函数是一个先增后减的函数，满足三分法。。然后推出L和人到灯的水平距离x满足函数式L=D-x+H-D*(H-h)/x。然后x的初始值可以由相似三角形得到h/H=(D-x)/D => x=D-D*h/H，x最大值为D，即确定了l一开始为D-D*h/H，r一开始为D。

参考代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double D,H,h,l,r,mid,mmid;
int t;
double getf(double x)
{
    return D-x+H-D*(H-h)/x;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>H>>h>>D;
        l=(H-h)*D/H;
        r=D;
        while (l<r-0.0000000001)
        {
            mid=(l+r)/2;
            mmid=(mid+r)/2;
            if (getf(mid)>=getf(mmid)) r=mmid;
            else l=mid;
        }
        printf("%.3lf\n",getf(mid));
    }
    return 0;
}