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

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

程序员文章站 2023-11-12 09:05:46
二分法除了可以进行有序查找、解方程等外,还可以用来解决一些实际问题。这些问题中,非常典型的应用就是“最小化最大值问题”和“最大化最小值问题” “最小化最大值问题”和“最大化最小值问题”在优化问题中比较常见,简单来说,“最小化最大值”是为了压制优化目标中表现最突出的成分,“最大化最小值”为了提升优化目 ......

      二分法除了可以进行有序查找、解方程等外,还可以用来解决一些实际问题。这些问题中,非常典型的应用就是“最小化最大值问题”和“最大化最小值问题”

      最小化最大值问题最大化最小值问题在优化问题中比较常见,简单来说,最小化最大值是为了压制优化目标中表现最突出的成分,最大化最小值为了提升优化目标中表现最差的成分。

      (1)最小化最大值问题

      一般来说,优化时考虑的是目标函数的最大化或最小化的问题。但是在某些情况下,则要求最大值的最小化才有意义。例如,在城市规划中需要确定急救中心、消防中心的位置,可取的目标函数应该是到所有地点最大距离的最小值(即急救中心、消防中心的建设位置应保证它到最远需求点的距离尽可能小),而不是到达所有目的地距离和的最小值。因为城市同时发生事故或同时着火的几率极低,因此更多应该考虑如何降低最恶劣情况的影响,即使是最远的地方出事了,中心到它们的距离也能达到最小。

      (2)最大化最小值问题

      这个问题在通信链路中应用比较多,如基站同时和多用户通信,每个基站到用户的通信为一个通信链路,且基站的发射功率是固定的。为了保证所有的通信链路都正常工作,应该去优化最差链路的通信情况,降低信道较好链路的基站发射功率,增加信道较差链路的基站发射功率,这是一个最大化最小值问题。

 【例1】数列分段。

题目描述

对于给定的一个长度为n的正整数数列a-i,现要将其分成m(m≤n)段,并要求每段连续,且每段和的最大值最小。

关于最大值最小:

例如一数列4 2 4 5 1要分成3段

将其如下分段:

[4 2] [4 5] [1]

第1段和为6,第2段和为9,第3段和为1,和最大值为9。

将其如下分段:

[4] [2 4] [5 1]

第1段和为4,第2段和为6,第3段和为6,和最大值为6。

并且无论如何分段,最大值不会小于6。

所以可以得到要将数列4 2 4 5 1要分成3段,每段和的最大值最小为6。

输入输出格式

输入格式:

第1行包含两个正整数n,m(n≤100000,m≤n)。

第2行包含n个空格隔开的非负整数ai(ai之和不超过10^9)

输出格式:

一个正整数,即每段和最大值最小为多少。

输入输出样例

输入样例#1: 

5 3

4 2 4 5 1

输出样例#1: 

6

      (1)编程思路。

      要解决这个最小化最大值的问题,基本思路就是选取任意一个范围(输入数组的最大值到数组所有元素的和),然后在这个范围内进行二分法,每次把范围的中间值mid当作最小值,然后判断在mid值下数组是否能够被分为m个部分。如果判断出值为mid时可以将数组分成m个部分,就先让mid变大再试试,即增大下界(left=mid+1);如果分不成m个部分,说明当前的mid太大了,就先让mid变小再进行判断,即减小上界(right=mid)。直到求出一个最大的mid就是最终的答案。

      (2)源程序。

#include <stdio.h>

int n,m;

int a[100000];

bool judge(int mid)

{

     int sum=0;

     int count=0;

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

     {

             sum += a[i];

             if(sum>mid)

             {

                 sum=a[i];

                 count++;        

             }

     }

     if ((count+1)<=m)

        return 1;

     return 0;

}

int main()

{

    scanf("%d%d",&n,&m);

    int left=-1,right=0,mid,i;

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

    {

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

       right += a[i];

       if(a[i]>left)

       {

          left = a[i];            

       }

    } 

    while(left<right)

    {

         mid=(left+right)/2;

         if(judge(mid))

         {

            right = mid;               

        }

        else

        {

          left = mid+1;

        }

    }

    printf("%d\n",left);

   return 0;

}