是什么问题
by Stephen_Curry @ 2019-05-25 20:28:23
编译通过了吗
by Stephen_Curry @ 2019-05-25 20:28:37
@[Stephen_Curry](/space/show?uid=212267) 过了啊,第四个点WA了
by shajjl @ 2019-05-25 20:45:15
@[shajjl](/space/show?uid=102377) 同求,#4过不了
by DIXIN @ 2019-06-17 21:46:54
同问
by BIG_Showers @ 2019-07-21 20:34:40
同问
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],n,m;
bool check(int x)
{
int s = 1,sum = 0;
for(int i = 1;i <= n;i++)
{
if(a[i]+sum>x){s++;sum = a[i];}
else sum+=a[i];
}
if(sum == 0)s--;
return s<=m;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)cin >> a[i];
int l = 1,r = 1000000000;
while(l <= r)
{
int mid = (l+r)/2;
if(check(mid))r = mid-1;
else l = mid+1;
}
cout << l;
return 0;
}
```
by max0810 @ 2019-08-01 12:34:45
同问
```
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],sum;
bool valid(int size){
int group=1,rest=size;
for(int i=1;i<=n;i++){
if(rest>=a[i])rest-=a[i];
else group++,rest=size-a[i];
}
return group<=m;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int l=1,r=sum;
while(l<r){
int mid=(l+r)/2;
if(valid(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
```
by Ryan_ @ 2019-08-07 10:03:54
我懂了,左端点要取数字中的最大值
by Ryan_ @ 2019-08-07 10:09:54
同问
```#include<stdio.h>
int a[10000],n,m;
int check(int x){
int num=m,i=0;
while(1){
int j=i;
while(a[j]-a[i]<=x&&j<n)j++;
num--;
if(j==n||num<0){
if(j==n&&a[j]-a[i]>x)num--;
break;
}i=j-1;
}if(num>=0)return 1;
else return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=2;i<=n;i++)a[i]+=a[i-1];
int l=0,r=a[n],mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}if(check(r))printf("%d",r);
else printf("%d",l);
return 0;
}
by VTloBong @ 2019-08-09 20:31:46
[WA on 4 的请进](https://www.luogu.org/discuss/show/55522)
by Andrew82 @ 2019-08-14 21:34:45