欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二分法(三):采用二分法解决“最大化最小值问题”

程序员文章站 2022-06-09 13:28:41
【例1】跳石头。 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。 ......

【例1】跳石头。

题目描述

一年一度的跳石头比赛又要开始了!

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 n 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 mm 块岩石(不能移走起点和终点的岩石)。

输入输出格式

输入格式:

第一行包含三个整数 l,n,m,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证0 ≤ m ≤ n ≤ 50,000,1 ≤ l ≤ 1,000,000,000。。

接下来 n 行,每行一个整数,第 i 行的整数 d_i( 0 < d_i < l), 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式:

一个整数,即最短跳跃距离的最大值。

输入输出样例

输入样例#1:

25 5 2

2

11

14

17

21

输出样例#1:

4

说明

输入输出样例 1 说明:将与起点距离为 2和 14的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17的岩石跳到距离 21的岩石,或者从距离 21的岩石跳到终点。

      (1)编程思路。

      这道题要求一堆最小距离里面的最大值,是一道典型的最小值最大化问题,可以采用二分法解决。

      1)首先将距离排序,虽然石子顺序是确定的,但是排完序不影响它们之间的差值,这个是肯定的。

      2)确立二分的上下界,上界right就是河流的宽度l,下界left就是最小石头间距。

      3)然后在上下界之间二分,二分时需要确定判断条件,测试当前的mid值。

      判断当前mid值的方法是这样的:循环所有的石头间距,逐个累加,如果没有超过当前mid,意味着该石头可以搬开(这是为了保证最小跳跃长度为mid,小于mid距离的石头不能往上面跳,因为如果一跳就会出现比mid更小的距离了),即搬石头数x++,如果超过了当前mid,则不能搬了(需要跳到这个石头上落下脚),而且要把此时的累加距清零,以便后一段继续如此处理。

      根据循环之后的结果,如果搬石头数目x超过了规定的m,说明mid值过大,于是上界缩小right变为mid-1:如果x小于m,则在跳跃时还可以跳过m-x个石头,说明mid值偏小,则下界增大left变为mid+1……由此二分完毕即得最大化最小间距。

      (2)源程序。

#include <iostream>

#include <algorithm>

using namespace std;

int d[50005],l,n,m; 

bool judge(int mid)

{

         int start=0,x=0,i; // start表示每次落脚点的坐标,每落一次地更新一次start

         for(i=1;i<=n;i++)

         {

                   if (d[i]-start<mid)

                      x++;   // x表示去掉的石头数,如果mid大于要跳的距离,就跳过当前这个石头,此时x++ 

                   else

                      start=d[i];  // 此时落在石头上

         }

         if (l-start<mid)   // 判断最后一跳跳的距离要是小于mid的话那是不可以的

             return false;

         if(x>m)          //  要是x>m就说明最小距离mid太大啦

             return false;

         return true;

}

int main()

{

     int left,right,mid,ans,min = 0x7fff,i;

     cin>>l>>n>>m;

     for(i=1;i<=n;i++)

          cin>>d[i];

     d[0] = 0; 

     d[n + 1] = l;

     sort(d,d+(n+1));

     for(i = 0; i <= n; i++) 

        if (d[i+1]-d[i]<min) 

             min = d[i+1]-d[i]; 

     left = min, right = l;

     while(left<=right)

     {

          mid=(left+right)/2;

          if (judge(mid))

           {

                     left=mid+1;

                     ans=mid;

            }

            else

                   right=mid-1;

     }

     cout<<ans<<endl;

     return 0;

}

      将此源程序提交给poj  3258 “river hopscotch”,可以accepted。

 【例2】好斗的牛(poj 2456 翻译而来)。

 题目描述

 农夫约翰建造了一座有n(2<=n<=100000)间牛舍的小屋,牛舍排在一条直线上,第i间牛舍在xi(0<=xi<=1000000000)的位置。但是约翰的c(2<=c<=n)头牛不喜欢牛舍这种布局,而且几头牛如果冲到同一个隔间里,它们就要发生争斗。约翰为了防止牛之间互相攻击互相伤害,因此决定把每头牛都放在离其它牛尽量远的牛舍,使任意两头牛之间的最小距离尽可能大,那么,这个最大的最小距离是多少呢?

输入格式

第一行是用空格分隔的两个整数n,c

第二行为n个用空格隔开的整数,表示位置xi

输出格式

输出仅一个整数,表示最大的最小距离值

样例输入

5 3

1 2 8 4 9

样例输出

3

样例解释

 把牛放在第1,4, 8 间,这样最小的距离值是3

      (1)编程思路。

      将c头牛放在n个点中的c个点上的最大距离是:dis=(pmax-pmin)/(c-1)。(最大的坐标-最小的坐标再除以c-1)。

      首先对隔间位置xi从小到大排序,然后以left=0为下界,以right=dis为上界通过二分法求这个最大的最小距离。

      假设当前的最小距离为mid,如果判断出最小距离为mid时可以放下c头牛,就先让mid变大再试试,即增大下界(left=mid+1);如果放不下c头牛,说明当前的mid太大了,就先让mid变小再进行判断,即减小上界(right=mid-1)。直到求出一个最大的mid就是最终的答案。

      (2)源程序。

#include <iostream>

#include <algorithm>

using namespace std;

const int n = 100005;

int p[n], n, c;

bool judge(int x)

{

    int cnt = 1, tmp = p[0];

    for(int i = 1; i < n; i++)

    {

        if(p[i] - tmp >= x)

        {

            cnt++;

            tmp = p[i];

            if(cnt >= c)    //可以放下c头牛

                return true;

        }

    }

    return false;

}

int main()

{

    int i,low,high,mid;

    cin>>n>>c;

    for(i=0;i<n;i++)

        scanf("%d",&p[i]);

    sort(p,p+n);

    high=(p[n-1]-p[0])/(c-1);

    low=0;

    while(low<=high)

    {

         mid=(low+high)/2;

         if (judge(mid)) low=mid+1;

         else high=mid-1;

    }

   cout<<low-1<<endl;

   return 0;

}