最大值最小化

题目描述
把一个包含n个正整数的序列划分成m个连续的子序列（每个正整数恰好属于一个序列）。设第i个序列的各数之和为S(i)，如何让所有S(i)的最大值尽量小？
例如序列1 2 3 2 5 4，划分成3个序列的最优方案为1 2 3 | 2 5 | 4，其中S(1)=6, S(2)=7, S(3)=4，最大值为7；如果划分成1 2 | 3 2 | 5 4，则最大值为9，不如刚才的好。
n≤10^6，所有数之和不超过10^9。

输入描述
可能有多个输入样例。
每个样例第一行输入两个整数n和m，第二行输入n个整数。

输出描述
输出所有子序列划分中子序列和的最大值的最小值。

输入样例
6 3
1 2 3 2 5 4

输出样例
7

zhc的code：

//最大值最小化
#include<iostream>
using namespace std;
bool ok(int *data,int num,int groups,int mid);//判断mid是否可以做子序列和的最大值

int main(){
    int num;//数字个数
    while(cin >> num ){
    int groups; //划分数
    cin >> groups ;
    int data[num] ;
    int sum= 0 ;
    int min = 0 ;//子序列和的最大值的下界
    for(int i = 0 ; i < num ; ++i){
        cin>>data[i] ;
        sum+=data[i] ;
        if(data[i]>min) min = data[i] ;//子序列和的最大值的下界= max_of_data[i]
    }
    int max=sum-groups+1 ;//子序列和的最大值的上界,其余n-1组都只有1个1时
    int min_of_max ;//最小的子序列和的最大值
    while( min<=max){
        int mid = (min+max)/2 ;
        if(ok(data,num,groups,mid)){ //mid可以做子序列和的最大值时
            max=mid-1;
            min_of_max = mid ;
            }
        else  min = mid+1 ; //mid不能做子序列和的最大值时
    }
    
    cout << min_of_max <<endl ;
    }
}

bool ok(int *data,int num,int groups,int mid){
    int sum = 0 ;
    int groups0 = 1; //记录按子序列和的最大值为mid时的划分数
    for(int i = 0 ; i < num ; ++i){
        sum+=data[i] ;
        if(sum > mid){ //如果sum+data[i]>mid时就
            sum=data[i] ;
            ++groups0 ;
        }
    }
    if(groups0 <= groups) return true ;//组数和小于等于groups，说明可以分组
    else return false ;
}

Yizuodi的答案

#include <iostream>
using namespace std;

bool v(int *data, int size, int partnum, int mid_of_max) //判断mid_of_max是否可以做子序列和的最大值
{
    int sum = 0;
    int partnum_new = 1; //记录按子序列和的最大值为mid时的划分数
    for (int i = 0; i < size; ++i)
    {
        sum += data[i];
        if (sum > mid_of_max)//如果sum加上data[i]大于mid_of_max，那么就划分新的子序列
        {
            sum = data[i];
            ++partnum_new;//子序列数量+1
        }
    }
    if (partnum_new <= partnum) return true; //组数和小于等于partnum，说明可以划分出指定子序列
    else return false;
}

int main()
{
    int size, partnum; //整数个数,划分个数
    while (cin >> size)
    {
        cin >> partnum;
        int data[size]; //用于存储输入的整数
        int sum_of_int = 0;
        int lowerbound_of_max = 0; //子序列和的最大值的下界
        for (int i = 0; i < size; ++i)
        {
            cin >> data[i];
            sum_of_int += data[i];
            if (data[i] > lowerbound_of_max)
            {
                lowerbound_of_max = data[i]; //data[i]中最大值为子序列和的最大值的下界
            }
        }
        int upperbound_of_max = sum_of_int - partnum + 1; //子序列和的最大值的上界,这里的情况为其余n-1组仅含一个1
        int min_of_max=lowerbound_of_max;             //子序列和的最大值的最小值
        while (lowerbound_of_max <= upperbound_of_max)
        {
            int mid_of_max = (lowerbound_of_max + upperbound_of_max) / 2;
            if (v(data, size, partnum, mid_of_max))//mid_of_max可以做子序列和的最大值时
            {
                upperbound_of_max = mid_of_max - 1;//看看mid_of_max小一点能否找到更小的最大值
                min_of_max = mid_of_max;//把已找到的进行记录
            }
            else//mid_of_max不能做子序列和的最大值时
            {
                lowerbound_of_max = mid_of_max + 1;//看看mid_of_max大一点能否找到最大值
            }
        }
        cout << min_of_max << endl;
    }
}