# 14163: 【原4163】矮人的宝藏

### 题目描述

author: Yifan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4163

## 样例输入

``````5 3
4 2 4 5 1
``````

## 样例输出

``````6
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int val_data[100009] = { 0 };

int main() {
int n, m;
scanf("%d %d", &n, &m);

int left = 0, right = 0;

for (int i = 0; i < n; ++i) {
scanf("%d", &val_data[i]);
right += val_data[i];
left = val_data[i] > left ? val_data[i] : left;
}

int right_ans = 0;

while (left <= right) {
auto mid = (left + right) >> 1;
int cnt = 0;
for (int i = 0; i < n; ) {
int cur_ans = 0;
++cnt;
for (int j = i;; ++j) {
cur_ans += val_data[j];
if (cur_ans > mid) {
i = j;
break;
}
if (j == n - 1) {
i = j + 1;
break;
}
}
}
if (cnt <= m) {
right_ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}

cout << right_ans;

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
int n,m,a[100001],l,r,mid,ans,cnt,cur;
bool flag;
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i)
scanf("%d",&a[i]);
l=0;
r=1000000000;
while (l<=r){
mid=(l+r)/2;
cnt=0;
cur=0;
flag=true;
for (int i=0;i<n;++i){
if (a[i]>mid){
flag=false;
break;
}
if (cur+a[i]>mid){
cur=0;
cnt++;
}
if (cnt==m){
flag=false;
break;
}
cur+=a[i];
}
if (flag){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#define MAX_N 100010
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n, m;
bool flag;
int a[MAX_N];
char ch = getchar(); int res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
int main() {
int l = 0, r = (int)1e9 + 5;
for (register int i = 0; i < n; ++i) {
l = max(l, a[i]);
}
while (l < r) {
int mid = (l + r) >> 1;
flag = true;
int cnt = 1, cur_sum = 0;
for (register int i = 0; i < n; ++i)
if (cur_sum + a[i] > mid) {
cur_sum = a[i];
++cnt;
if (cnt > m) {
flag = false; break;
}
}
else cur_sum += a[i];
if (flag) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
``````