寒假专题训练--二分/三分

专题 二分 三分

VJ地址

A - Strange fuction

HDU - 2899

• 题意
  给定一个函数F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) ，其中y为常数。y的范围为(0 < Y <1e10)。
  给定y值，求出相对应的函数最大值。
• 思路
  求导可得F(x)的一阶导数为f1(x)=42*x^6+48*x^5+21*x^2-10*x-y;其二阶导数为f2(x)=252*x^5+240*x^4+42*x-10。
  通过对一阶导数与二阶导数的分析可知，在[0,100]中存在一个x0，使得f1(x0)=0，且当x=x0时，F(x)取得最小值。
  通过二分查找，找到x0值。
• AC代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
double fun1(double x,double y)
{
    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 fun2(double x,double y)
{
    return 42*x*x*x*x*x*x+48*x*x*x*x*x+21*x*x+10*x-y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        double y;
        scanf("%lf",&y);
        double l=0,r=100;
        while(r-l>1e-8)
        {
            double m=l+(r-l)/2;
            if(fun2(m,y)<=0)
                l=m;
            else
                r=m;
        }
        printf("%.4f\n",fun1(l, y));
    }
    return 0;
}

B - Can you find it?

HDU - 2141

• 题意
  给出两个数组A,B,C和一个数X。求能在否在三个数组中各取一个元素，使得取出的三个元素之和等于X。
• 思路
  三个元素的取法或者说组合方式最多有500*500*500种，显然不能直接粗暴地将所有的组合方式列出然后进行查找。
  此时，可将前两个数组的所有组合方式构成一个新数组"AB"，例如A={1,2,3},B={1,2,3},则AB={2,3,4,5,6}。即可看做从数组"AB"与"C"中各取一个元素，然后判断其和值是否满足条件。
  至此，可以使用二分查找。
  这样，构成AB的复杂度O(n)=500*500=250000,判断的负责度为O(n)=500*(ln250000)=500*12。
• AC代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long a[505],b[505],c[505];
long long ab[250005];
int main()
{
    int L,M,N;
    int kase=0;
    while(~scanf("%d%d%d",&L,&M,&N))
    {
        for(int i=0;i<L;i++)
            scanf("%lld",&a[i]);
        for(int i=0;i<M;i++)
            scanf("%lld",&b[i]);
        for(int i=0;i<N;i++)
            scanf("%lld",&c[i]);
        for(int i=0;i<L;i++)
            for(int j=0;j<M;j++)
                ab[i*M+j]=a[i]+b[j];
        sort(ab, ab+L*M );
        int s;
        scanf("%d",&s);
        printf("Case %d:\n",++kase);
        while(s--)
        {
            long long key;
            scanf("%lld",&key);
            int flag=0;
            for(int i=0;i<N;i++)
            {
                int l=0,r=L*M;
                long long k=key-c[i];
                while(r-l>1)
                {
                    int m=l+(r-l)/2;
                    if(ab[m]<=k)
                        l=m;
                    else
                        r=m;
                }
                if(ab[l]==k)
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}

C - Monthly Expense

POJ - 3273

• 题意
  已知接下来N天每天的花费，欲将N天分为连续的M组，任一个组中各天花费之和不能超过一个限度。想出一种分法，使得这个限度最小，求出这个最小的限度。

• 思路
  所求最小限度必然在一个特定的区间内，这个区间的最小值为花费最多的那一天的花费，最大值为所有天的花费之和。可对这个区间进行二分查找。
  如果当前找的限度为K，那么以K为限度进行分组，若组数大于M，则说明K值小了；如果组数小于M，则说明K值大了。
  需要注意的是，所求解显然是唯一的。意思是即便组数等于M，当前的K也不一定为最小限度，应继续查找直到循环结束。
  另附在网上看到的很棒的一个题解

• AC代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,m,sum,ma;
int a[100005];
int arr(int x)
{
    int sx=0,num=1;
    for(int i=0;i<n;i++)
    {
        sx+=a[i];
        if(sx>x)
        {
            sx=a[i];
            num++;
        }
    }
    return num;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d",&a[0]);
    sum=a[0];
    ma=a[0];
    for(int i=1;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
        if(ma<a[i])
            ma=a[i];
    }
    int l=ma,r=sum;
    while(l<r)
    {
        int mid=l+(r-l)/2;
        if(arr(mid)<=m)
            r=mid-1;
        else
            l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}

D - River Hopscotch

POJ - 3258

• 题意
  从起点到终点距离为L个单位长度。同时起点与终点之间有N个石头，起点与终点上也有石头。已知每个石头距离起点的距离。现在要移去起点与终点之间的M个石头，要使距离最近的两块石头之间的距离尽可能大，求出这个距离。
• 思路
  先按照石头的原始位置排好顺序。
  显然所求的尽可能大的相邻石块间最短距离，是以相邻最近的两块石头之间的距离为下限，以起点与终点之间的距离为上限的。
  可以用二分查找的方式来确定这一距离。假设这一距离为K，那么根据K可确定移走的石头数目，若这个数目大于M，说明K大了；若这个数目小于M，则说明K取小了。注意这个数目等于M时，当前的K并不一定是所求解。
  注意在根据距离K，确定需移走的石头数目时，终点与其前面的那块石头间的距离也要进行处理。
  不懂的地方：if (sum<=mid) //why <= ？？
• 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
    int l,n,m,le,ri;
    int dis[50005];
    scanf("%d%d%d",&l,&n,&m);
    dis[0]=0;
    dis[n+1]=l;
    le=l;
    ri=l;
    for(int i=1;i<=n;i++){
        scanf("%d",&dis[i]);
    }
    sort(dis,dis+n+2);//按石头的原始位置排列
    for(int i=1;i<=n+1;i++){
        if (dis[i]-dis[i-1]<le)
        {
            le=dis[i]-dis[i-1];
        }
    }
    while(le<ri){
        int sum=0,mid=le+(ri-le)/2,count=0;
        for (int i = 1; i <= n+1; ++i)//到n+1是为了对最后一段进行处理
        {
            sum+=dis[i]-dis[i-1];
            if (sum<=mid)//why <= ？？感觉是因为贪心算法
            {
                count++;
            }else{
                sum=0;
            }
        }
        if(count<=m){
            le=mid+1;
        }else{
            ri=mid;
        }
    }
    printf("%d\n",le);
    return 0;
}

E - Communication System

[POJ - 1018]

We have received an order from Pizoor Communications Inc. for a
special communication system. The system consists of several devices.
For each device, we are free to choose from several manufacturers.
Same devices from two manufacturers differ in their maximum bandwidths
and prices. By overall bandwidth (B) we mean the minimum of the
bandwidths of the chosen devices in the communication system and the
total price (P) is the sum of the prices of all chosen devices. Our
goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤
10), the number of test cases, followed by the input data for each
test case. Each test case starts with a line containing a single
integer n (1 ≤ n ≤ 100), the number of devices in the communication
system, followed by n lines in the following format: the i-th line (1
≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers
for the i-th device, followed by mi pairs of positive integers in the
same line, each indicating the bandwidth and the price of the device
respectively, corresponding to a manufacturer. Output Your program
should produce a single line for each test case containing a single
number which is the maximum possible B/P for the test case. Round the
numbers in the output to 3 digits after decimal point.

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649

• 题意
  构筑一个系统需要几种元件各一个，任一种元件都有多种生产方式，用不同生产方式生产的同一种元件，带宽与价格不同。
  一个系统其总带宽是构成它的那几个元件中带宽最小的那个元件的带宽，其总价是构成它的那几个元件的价格之和。
  求一个系统，带宽/总价的可能最大值。
• 思路
• 代码

F - Light Bulb

[ZOJ - 3203]

Compared to wildleopard's wealthiness, his brother mildleopard is
rather poor. His house is narrow and he has only one light bulb in his
house. Every night, he is wandering in his incommodious house,
thinking of how to earn more money. One day, he found that the length
of his shadow was changing from time to time while walking between the
light bulb and the wall of his house. A sudden thought ran through his
mind and he wanted to know the maximum length of his shadow.

Input

The first line of the input contains an integer T (T <= 100),
indicating the number of cases.

Each test case contains three real numbers H, h and D in one line. H
is the height of the light bulb while h is the height of mildleopard.
D is distance between the light bulb and the wall. All numbers are in
range from 10-2 to 103, both inclusive, and H - h >= 10-2.

Output

For each test case, output the maximum length of mildleopard's shadow
in one line, accurate up to three decimal places..

Sample Input

3
2 1 0.5
2 0.5 3
4 3 4

Sample Output

1.000
0.750
4.000

• 题意
  灯高H，人高h，灯距离墙壁L。人在灯与墙之间，求人的影子长度（在地面与墙上的连续的两部分之和）的可能最大值。
• 思路
• 代码