寒假第一练 二分和三分

二分三分专题

[题目][A]

Strange fuction
题目大意：
对于一个函数
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)对于T(1<=T<=100)组数据，每组数据为y(0 < Y < 1e10)，输出函数的最小值。

解题思路：
F(x)为一个凹函数，对于每个y要求函数的最小值。三分函数自变量x的区间。即设置4个变量，l=0,r=100,lmid=l+(r-l)/3,rmid=r-(r-l)/3.然后在左右区间精度范围内不断更新l和r.当lmid的函数值大于或等于rmid的函数值，则更新l为lmid，否则更新r为rmid.直到l+eps>=r。
时间复杂度O(log3n)，空间复杂度O(1).

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
double y;
double cal(double x)
{
    return 6*x*x*x*x*x*x*x + 8*x*x*x*x*x*x + 7*x*x*x + 5*x*x - y*x;
}
double solve(double l,double r)
{
    double lmid,rmid;
    double eps = 1e-7;
    while(l + eps < r)
    {
        lmid = l + (r-l) / 3;
        rmid = r - (r-l) / 3;
        if(cal(lmid) < cal(rmid)) r = rmid;
        else l = lmid;
    }
    return cal(l);
}
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
        scanf("%lf",&y);
        printf("%.4lf\n",solve(0,100));
   }
    return 0;
}

[题目][B]

Can you find it?
题目大意：
A序列：由L个数据组成，B序列：由N个数据组成，C序列：由M个数据组成。(1<= L,N,M <= 500)在3个序列中，分别选出一个数据，然后判断这三个数据之和是否等于给定的X。X有S个(1<= S <= 1000).

解题思路：
如果直接判断Ai+Bj+Ck==X是否成立，时间复杂度为： 500*500*500*log(500*500*500) * 1000,而改变一下，即判断Ai+Bj == X-Ck是否成立，时间复杂度为： 500*500*log(500*500) * 1000*500.所以先求a[i]+b[j]的值，排好序，然后求这个序列中是否有值等于X-c[k]，即二分搜索。注意定义好数据类型，X可能很大，所以应该把X,a[maxn],b[maxn],c[maxn]定义为long long 类型。
时间复杂度O(L*M*log(L*M) *S*N),空间复杂度O(1).

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 505;
const int absize = 505*505;
long long int a[maxn],b[maxn],c[maxn];
int len;
long long ab[absize];
int binarysearch(long long int x)
{
    int l = 0,r = len-1;
    int mid;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(ab[mid] == x) return 1;
        else if(ab[mid] > x)
        {
            r = mid-1;
        }
        else l = mid+1;
    }
    return 0;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int l,n,m;
    int i,j;
    int k = 0;
    long long int x;
    int s;
    while(scanf("%d%d%d",&l,&n,&m) != EOF)
    {
        len = 0;
        for(i = 0; i < l; i++)
            scanf("%lld",&a[i]);
        for(i = 0; i < n; i++)
            scanf("%lld",&b[i]);
        for(i = 0; i < m; i++)
            scanf("%lld",&c[i]);
        for(i = 0;i < l;i++)
        {
            for(j = 0;j < n;j++)
            {
                ab[len++] = a[i]+b[j];
            }
        }
        sort(ab,ab+len);
        sort(c,c+m);
        scanf("%d",&s);
        k++;
        printf("Case %d:\n",k);
        while(s--)
        {
            scanf("%lld",&x);
            if(x < ab[0]+c[0] || x > ab[len-1]+c[m-1])
            {
                printf("NO\n");
            }
            else
            {
                for(i = 0; i < m; i++)
                {
                    if(binarysearch(x-c[i]))
                    {
                        printf("YES\n");
                        break;
                    }
                }
                if(i == m) printf("NO\n");
            }
        }
    }
    return 0;
}

[题目][C]

Monthly Expense

题目大意：
给出N天(1 ≤ N ≤ 100,000)中，每天的金钱数money(1 ≤ moneyi ≤ 10,000),把这N天不改变顺序分成M份(1 ≤ M ≤ N)，然后求出这M部分中money和的最大值，要求对于不同的划分，最大值要最小。

解题思路：
设C(x):M个部分中的money的最大值小于等于x，即：任一部分的money的和均小于等于x。然后求x的最小值。那么可以对x(max of money -1 < x <= sum of money)二分。初始化l = max-1,r = sum，mid = (l+r) / 2，x = mid，然后通过贪心可以，初始化第一部分为money1，然后合并下一天的money保证总和不大于x，即floor(moneyi + x)对应的j为前一部分的终点，继续往下贪心计算划分的部分数，然后比较划分数与M。如果划分数小于等于M，则更新r=mid,否则更新l=mid，重新计算mid的值，也就是x的假设值。直到l+1>=r停止更新返回r。
时间复杂度O(n*log(n*money))，空间复杂度O(1)

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define ll long long
using namespace std;
const ll maxn = 100000+5;
ll money[maxn];
ll n,m;
ll cal(ll weigh)
{
    ll cw = money[1];
    int i = 1;
    ll cnt = 0;
    while(i <= n)
    {
        while(i <= n && cw <= weigh)
        {
            i++;
            cw += money[i];
        }
        cnt++;
        if(i <= n)
        cw = money[i];
    }
    return cnt;
}
ll solve(ll l,ll r)
{
    ll mid;
    while(l + 1 < r)
    {
        mid = (l+r)/2;
        if(cal(mid) <= m)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    return r;
}
int main()
{
   // freopen("in.txt","r",stdin);
    ll i;
    ll sum = 0,mmax = 0;
    scanf("%lld%lld",&n,&m);
    for(i = 1;i <= n;i++)
    {
        scanf("%lld",&money[i]);
        if(mmax < money[i]) mmax = money[i];
        sum += money[i];
    }
    printf("%lld\n",solve(mmax-1,sum));
    return 0;
}

[题目][D]

River Hopscotch

题目大意：
在起点和终点相距L(1 <= L <= 1e9)的一条河中，起点和终点之间有N(0 <= N <= 5000)个石头，两个石头之间的距离为Di(0 < Di < L),现在要拿走M个石头(0 <= M <= N)，最大化相邻两个石头的距离的最小值。

解题思路：
设函数C(x):相邻的两个石头的最小距离大于等于x。即求x的最大值，可以选定x的范围为左闭右开。所以x的范围可以初始化为[0,l+1),然后对x[l,r)的范围进行二分，直到l+1 >= r,mid=(r+l)/2,每次二分后将mid代入贪心，从起点开始，取距离最大为mid，然后留下该石头，然后继续贪心，尽量留下最多的石头，然后比较留下的石头数和n-m的大小，如果留下的大于等于n-m，那么更新l=mid，否则更新r=mid。
时间复杂度O((n+2)*lo(n+2)(l+2)),空间复杂度O(1)。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 50000 + 10;
ll d[maxn],dlen;
ll num;
ll l,n,m;
ll cal(ll x)
{
    ll i,j;
    ll cnt = 0;
    i = 0,j = 1;
    while(j < dlen)
    {
        while(i < dlen-1 && j < dlen && d[j]-d[i] < x)
        {
            j++;
        }
        if(i < dlen-1 && j < dlen)
        {
            i = j;
            j = i+1;
        }
        cnt++;
    }
    return cnt-1;
}
ll solve(ll l,ll r)
{
    ll mid;
    while(l + 1 < r)
    {
        mid = (l + r) / 2;
        if(cal(mid) >= num) l = mid;
        else r = mid;
    }
    return l;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ll i;
    scanf("%lld%lld%lld",&l,&n,&m);
    num = n-m;
    d[0] = 0;
    for(i = 1;i <= n;i++)
        scanf("%lld",&d[i]);
    d[i] = l;
    dlen = i+1;
    sort(d,d+dlen);
    printf("%lld\n",solve(0,l+1));
    return 0;
}

[题目][F]

Light Bulb

题目大意：

T(T <= 100)组测试样例。
每行有实数H(灯的高度),h(人的高度),D(灯与墙之间的距离)，10^-2 <= H,h,D <= 10^3,H-h >= 10^-2.
输出这个人影子的最大长度，保留三位小数。

解题思路：

H,h,D和影子长度l满足 l=D-x+H-D*(H-h)/x;x是人到墙的距离。由公式性质知，先增后减，故可以用三分来求最大值。当三分左值和右值小于某个精度的时候，就返回现在的距离l，并计算出影子长度。

AC代码：

#include <iostream>
#include <cstdio>
using namespace std;
double H,h,D;
double cal(double x)
{
    return D-x+H-D*(H-h)/x;
}
double solve(double l,double r)
{
    double lmid,rmid;
    while(r - l > 1e-10)
    {
        lmid = l+(r-l)/3,rmid = r-(r-l)/3;
        if(cal(lmid) < cal(rmid)) l = lmid;
        else r = rmid;
    }
    return l;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf",&H,&h,&D);
        printf("%.3lf\n",cal(solve(D-h*D/H,D)));
    }
    return 0;
}