A62680 | 问题描述对于给定的一个长度为N的正整数数列A₁~Aₙ，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。例如，把以下长度为5的数列分成3段：4 2 4 5 1。一种分法是：[4 2][4 5][1]，每段和分别为6、9、1，最大值为9；另一种分法可以是：[4 2][4][5 1]，每段和分别为6、4、6，最大值为6。可以发现第二种方案是最大值最小的方案。#include<b…

问题描述

对于给定的一个长度为N的正整数数列A₁~Aₙ，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。

例如，把以下长度为5的数列分成3段：4 2 4 5 1。

一种分法是：[4 2][4 5][1]，每段和分别为6、9、1，最大值为9；

另一种分法可以是：[4 2][4][5 1]，每段和分别为6、4、6，最大值为6。

可以发现第二种方案是最大值最小的方案。

#include<bits/stdc++.h>
using namespace std;
int n, m, a[100005], ans;
bool check(int x){
    int tot =0, num = ①;
    for(int i=1; i<=n; i++){
        if(②){
            tot += a[i];
        }else{
            ③;
            num++;
        }
    }
    return num > m;
}
int main(){
int l=0, r=0;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
        l =max(l, a[i]);
        r += a[i];
}
    while(④){
        int mid = ⑤;
        if(check(mid)) l = mid +1;
        else r = mid;
    }    
    cout << l;
    return 0;
}