直接二分判断就好了。。裸题。。一开始把每个组的和初始化成给的mid了。。
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long ll; int n,m; const int N=1e5+5; int a[N]; inline bool pd(ll x) { int tot=1; ll sum=0; fo(i,1,n) { if (a[i]>x)return 0; if (sum+a[i]>x) { sum=a[i];tot++; if (tot>m)return 0; } else sum+=a[i]; } return 1; } int main() { scanf("%d%d",&n,&m); int l=0; ll r=0,ans; fo(i,1,n)scanf("%d",&a[i]); l=0,r=1000000000; while (l<=r) { ll mid=(l+r)>>1; if (pd(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%lld\n",ans); return 0; }