最大值最小化

描述

把一个包含n个正整数的序列划分成m个连续的子序列（每个正整数恰好属于一个序列）。设第i个序列的个数之和为S(i)，你的任务是让所有S(i)的最大值尽可能小。例如序列： 1 2 3 2 5 4 划分成3个序列的最有方案为： 1 2 3 | 2 5 | 4，其中S(1)、S(2)、S(3) 分别为 6 、7、 4，最大值为 7；如果划分成 1 2 | 3 2 | 5 4，则最大值为 9，不如刚才的好。n \(\leq\) \(10^6\)，所有数之和不超过 \(10^9\)。

分析

“最大值最小化”是一类常见的优化问题，此问题来自 刘汝佳 《算法竞赛入门经典》第一版 P151。最近也在学习优化（凸优化、二次规划等）方面的内容，故将此题摘录作为一个典型问题，同时也是转入博客园的第一篇随笔，哈哈～
将此问题转换为：
判断对一个给定的数值 M，能否找到一个序列划分，使得其最大值小于 M？
若能够找到，说明真实的序列划分的最大值的最小值必然小于等于M，那就将 M缩小一点
若不能找到，说明真实的序列划分的最大值的最小值必然大于等于M，那就将 M放大一点
对 M的放大缩小可以采取二分查找的方式（在很多优化问题中都是这样），这样就可以通过逼近的方式求解出 \(\arg\min\max\)问题

 
这道题的另一个关键点在于如何划分m个连续子序列，这不难解决，划分的时候尽量往右划分，因为我们最担心的就是最后一个序列的划分：只要当前子序列向右添加一个元素的和没有超过 M，并且能够保证对剩下的序列划分后（其实只要考虑剩下的序列一个元素划分成一个序列的情况），所有子序列个数之和等于m, 就一直往右合并；如果出现无法划分的极端情况，就说明 M不是我们寻找的答案，具体的可以参考下面的代码。

代码

bool divide(vector<int>& a, int lim, int m){
    //description: returns whether the max value of m divisions is lower than lim
    int p = 0;
    for(int i=0;i<m;++i){
        int sum = 0;
        while(sum<lim && p < a.size()-(m-i)+1){ //guarantee m divisions
            if(sum+a[p]<lim)
                sum += a[p++];
            else
                break;
        }
        if(!sum)
            return false;
    }
    if(p < a.size())
        return false;
    return true;
}

long long int L=0, R=100000000;
    int M = L + (R-L)/2;
    while(R-L>1){ //binary search        
        if(divide(a, M, m))
            R = M;        
        else
            L = M;        
        M = L + (R-L)/2;        
    }