文本框(nh2023xj5)

比赛题目

时间限制：C/C++ 1000MS，其他语言 2000MS

内存限制：C/C++ 256MB，其他语言 512MB

分数：100

描述

小慧把她学会的英文单词记录了下来，现在她希望在一个文本框里完全显示出她记录的单词库。已知这个文本框最多只能显示M行，小慧的单词库有N个单词，要求按原次序显示所有单词，每个单词至少要用一个空格分开，而且一个单词的所有字母必须放在同一行。问这个文本框至少需要多宽才能满足小慧的需求。

输入描述

第一行，两个正整数N，M。 第二行，N个正整数，表示每个单词的长度。

输出描述

能把所有单词显示出来的文本框的最少宽度。

用例输入 1

13 3

9 5 2 7 1 8 8 2 1 5 2 3 6

用例输出 1

26

用例输入 2

30 8

8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

用例输出 2

189

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,len,a[10000001];
bool check(int x){
    int cnt=0,s=0;
    for(int i=1;i<=n;i++){
        s+=a[i];
        if(s+a[i+1]>=x&&i!=n){
            cnt++;
            s=0;
        }
        else{
        	s++;
		}
    }
    return cnt<m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        len+=a[i];
        len+=1;
    }
    len--; 
    int l=0,r=len,mid=0;
    while(l+1<r){
    	mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    cout<<r;
    return 0;
}