利用二分的思想求最值有关问题

利用二分的思想求最值问题

在求最值问题里，我们最常见的方法是动态规划，回朔法。然而二分思想也是能够解决某一类最值问题，而且这一类最值问题会用明显的特征。

先来看题目hiho第38周题目：http://hihocoder.com/contest/hiho38/problem/1

将该题目稍微简化模型，意思就是求点到点的最长路径边的最小值。该题目是不能用动态规划的，因为并不存在动态转移方程。因此只能用回朔法。但是这类题目有明显的特征就是：我们一个确定2个值，left_value,right_value，left_value一定不满足题目要求，而right_value则一定满足题目要求。故我们要找的最小值一定是在区间[left_value,right_value]内，一点有序区间去寻找某个值就可以用二分的思想。该替思路如下：

利用二分的思想求最值有关问题

其中打红色方框的就是该类型题目的共性，不同的则是需要根据题意，编写不同的f(x)函数。

该题源代码(已accept)如下：

#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
#include<vector>
#include<algorithm>
#define PMAXN 10010
#define GMAXN 200010
using namespace std;

struct edge
{
    int id;
    int next;
    int value;
   // edge(int value，int _id=0,int _next=-1):id(_id),next(_next){}
};

int pnode[PMAXN];  //用来存放点
edge lines[GMAXN]; //用来存放边
bool vis[PMAXN];
int lines_index=0;    //边数组的索引下标
int n,m,k,t;

int key[GMAXN]; //用来存放边权
int key_index=0;

void add(int l,int r,int value)
{
    lines[lines_index].id=l;
    lines[lines_index].next=pnode[r];
    lines[lines_index].value=value;
    pnode[r]=lines_index++;
    lines[lines_index].id=r;
    lines[lines_index].next=pnode[l];
    lines[lines_index].value=value;
    pnode[l]=lines_index++;
}
//不能使用深搜，会超时，因为深搜会使用递归，数据太大真不好用
bool f(int x)
{
    memset(vis,false,sizeof(vis));
    queue<pair<int,int> > q;
    q.push(make_pair(1,0));
    vis[1]=true;
    while(!q.empty())
    {
        int node=q.front().first;
        int num=q.front().second;
        if(num>=k)
            return false;
        q.pop();
        for(int i=pnode[node];i!=-1;i=lines[i].next)
        {
            if(lines[i].value>x||vis[lines[i].id])
                continue;
            if(lines[i].id==t)
                return true;
            q.push(make_pair(lines[i].id,num+1));
            vis[lines[i].id]=true;;
        }
    }
    return false;

}

int BinaryAnswer(int left,int right)
{
    if(left==right-1)
        return right;
    int mid=(left+right)/2;
    if(f(key[mid]))
        return BinaryAnswer(left,mid);
    else
        return BinaryAnswer(mid,right);
}
int main()
{
    freopen("a.txt","r",stdin);
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=0;i<=n;i++)
        pnode[i]=-1;
    for(int i=0;i<m;i++)
    {
        int l,r,value;
        scanf("%d%d%d",&l,&r,&value);
        key[key_index++]=value;
        add(l,r,value);
    }
    sort(key,key+key_index);
    int *p=unique(key,key+key_index);
    key_index=p-key;
    if(f(key[0]))
        printf("%d",key[0]);
    else
        printf("%d",key[BinaryAnswer(0,key_index-1)]);
    return 0;
}

来看一到hiho上微软面试题，同样使用的是二分搜索。 http://hihocoder.com/problemset/problem/1095

源代码（已accept）如下：

#include<cstdio>
#define maxn 100010
int n,k;
int d[maxn]; //每一次的随机数
int hi,ho,ho_cup;
//true表示小ho赢
bool f(int t)
{
    hi=0,ho=0;
    int ho_cup=t;
    for(int i=0;i<n;i++)
    {
        if(ho_cup<=d[i])
        {
            hi++;
            ho_cup=0;
        }
        else
        {
            ho++;
            ho_cup-=d[i];
        }
        ho_cup+=t;

    }
    return ho>hi;

}
int BinarySearch(int l,int r)
{
    if(l==r-1)
        return r;
    int mid=(l+r)/2;
    if(f(mid))
        return BinarySearch(l,mid);
    else
        return BinarySearch(mid,r);

}
int main()
{
    freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",d+i);
    printf("%d",BinarySearch(0,k+1));
    return 0;
}

利用二分的思想求最值有关问题

相关推荐