二分答案，分别往尽量小的和尽量大的二分即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 #define inf 100000000000000ll int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int n,m,a[N]; int calc(ll k) { ll x=0;int cnt=0; for (int i=1;i<=n;i++) { x=max(0ll,x+a[i]); if (x>=k) cnt++,x=0; } return cnt; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4590.in","r",stdin); freopen("bzoj4590.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); ll l=1,r=inf,ans=-1; while (l<=r) { ll mid=l+r>>1; if (calc(mid)<=m) ans=mid,r=mid-1; else l=mid+1; } if (calc(ans)!=m) ans=-1; cout<<ans<<' '; if (ans==-1) return 0; l=1,r=inf; while (l<=r) { ll mid=l+r>>1; if (calc(mid)>=m) ans=mid,l=mid+1; else r=mid-1; } cout<<ans; return 0; }