CQUPT 二分

题解

HDU：2899 STRANGE FUNCTION
题意：
求一个函数在自变量处于0到100闭区间时候的最小值。
思路：
经过求导发现，此函数的二阶导数在定义域内恒大于0，则一阶导数单调递增，又因为在0和100这两个端点一阶导数的值肯定是异号的，所以一阶导数在定义域内有一个零点，原函数在定义域内有一个极小值点也是最小值点。最后就用二分不断逼近此点（一阶导数），达到精度的后几位就ok。
代码：

#include <bits/stdc++.h>
using namespace std;
double y;
double f1x(double t)
{
    return (42 * pow(t,6) + 48 * pow(t,5) + 21 * pow(t,2) + 10 * t - y);
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lf",&y);
        double x1 = 0,x2 = 100;
        while (fabs(f1x((x1 + x2)/2)) > 1e-8)
        {
            if (f1x(x1) * f1x((x1 + x2)/2) < 0)
                x2 = (x1 + x2)/2;
            else
                x1 = (x1 + x2)/2;
        }
        double tmp = (x1 + x2)/2;
        double res = 6 * pow(tmp,7) + 8 * pow(tmp,6) + 7 * pow(tmp,3) + 5 * pow(tmp,2) - y * tmp;
        printf("%.4f\n",res);
    }
    return 0;
}

HDU 2141 : CAN YOU FIND IT
题意：
给出三个数组，和一个数X，问是否能在3个数组中分别找到一个数，使得三个数相加等于X。
思路：
二分的一点小变化，即复杂度的改进，先把A，B数组的和存入一个新数组，对于每一个X-Ci，用二分法在新数组中寻找是否存在这样的一个数。
代码：

#include <bits/stdc++.h>
using namespace std;
int a[505];
int b[505];
int c[505];
int ab[255025];
int x[1005];
int myfind(int t,int edge)
{
    int left = 0,right = edge - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (ab[mid] == t)
            return 1;
        else if (ab[mid] > t)
            right  = mid - 1;
        else
            left = mid + 1;
    }
    return 0;
}
int main()
{
    int l,n,m,s;
    int cnt = 1;
    while(scanf("%d%d%d",&l,&n,&m) == 3)
    {
        int h = 0;
        for (int i = 0;i < l;i++)
            scanf("%d",&a[i]);
        for (int i = 0;i < n;i++)
            scanf("%d",&b[i]);
        for (int i = 0;i < m;i++)
            scanf("%d",&c[i]);
        scanf("%d",&s);
        for (int i = 0;i < s;i++)
            scanf("%d",&x[i]);
        sort(a,a+l);
        sort(b,b+n);
        sort(c,c+m);
        printf("Case %d:\n",cnt++);
        for (int i = 0;i < l;i++)
            for (int j = 0;j < n;j++)
                ab[h++] = a[i] + b[j];
        sort(ab,ab+h);
        for (int i = 0;i < s;i++)
        {
            int flag = 0;
            for (int j = 0;j < m;j++)
            {
                int tmp = x[i] - c[j];
                if (myfind(tmp,h))
                    flag = 1;
            }
            if (flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}

POJ 3273 : MONTHLY EXPENSE
题意：
给出n个数，要求把这n个数分成m个部分，使得每个部分的数的和的最大值最小。
思路：
二分+贪心，套路。
代码：

#include <stdio.h>
int n,m;
int cost[100010];
int solve(int money)
{
    int tmp = 0,_if = 1;
    for (int i = 0;i < n;i++)
    {
        if (tmp + cost[i] <= money) tmp += cost[i];
        else
        {
            tmp = 0;
            _if++;
            i--;
        }
    }
    return _if <= m;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 0;i < n;i++)
        scanf("%d",&cost[i]);
    int lb = -1,ub = 0;
    for (int i = 0;i < n;i++)
    {
        if (cost[i] > lb)
            lb = cost[i];
        ub += cost[i];
    }
    while(lb < ub)
    {
        int mid = (lb + ub) / 2;
        if (solve(mid)) ub = mid;
        else lb = mid + 1;
    }
    printf("%d\n",ub);
    return 0;
}

poj3258 river hopscotch
题意：
最大化最小值。有n个石头，两个岸，问可以移走m个石头的情况下两个障碍物之间距离最小的最大值是多少。
思路：
二分。QAQ我只能把这题记住了。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[50005];
int m,n,L;
int meet(int dis)
{
    int cnt = 0;
    int last = 0;
    for (int i = 1;i <= n+1;i++)
    {
        if (dis >= (a[i]-a[last]))
        {
            cnt++;
        }
        else
        {
            last = i;
        }
    }
    return cnt;
}
int main()
{
    scanf("%d%d%d",&L,&n,&m);
    a[0] = 0;
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    a[n+1] = L;
    sort(a+1,a+n+1);
    int low = 0,high = L;
    while (low <= high)
    {
        int mid = (low + high) >> 1;
        if (meet(mid) <= m) low = mid + 1;
        else high = mid - 1;
    }
    printf("%d\n",low);
    return 0;
}