#include<bits/stdc++.h> using namespace std; int n,m,a[1000005],l,r; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; l=max(l,a[i]); r+=a[i]; } int ans=0; while(l<=r){ int mid=(l+r)/2; int sum=0,cnt=1; for(int i=1;i<=n;i++){ if(sum+a[i]<=mid){ sum+=a[i]; }else{ sum=a[i]; cnt++; } } if(cnt<=m){ r=mid-1; ans=mid; }else l=mid+1; } cout<<ans; return 0; }

简单易懂

#include<bits/stdc++.h> using namespace std; int n, m, a[100005]; bool func(int x) { for (int i = 1; i <= n; i++) { int j = i, sum = 0; cnt++; while (j <= n && sum + a[j] <= x) sum += a[j++]; i = j - 1; } return cnt <= m; } int main(){ cin >> n >> m; int maxn = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; maxn = max(maxn,a[i]); } int l = maxn, r = 1e9, ans; while (l <= r) { int mid = (l + r) / 2; if (func(mid)) { r = mid - 1; ans = mid; } else l = mid + 1; } cout << ans; return 0; }

#include <bits/stdc++.h> using namespace std; const int N=1e5+6; int n, m, a[N], l=0, r=0; int main() { cin >> n >> m; for (int i=1; i<=n; i++) { cin >> a[i]; if (l<a[i]) l = a[i]; r += a[i]; } }

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

5 3 4 2 4 5 1

#include<bits/stdc++.h> using namespace std; const int c=10e5+5; int n,m,a[c]; int main(){ cin>>n>>m; int l=0,r=0; for(int i=1;i<=n;i++){ cin>>a[i]; l=max(a[i],l); r+=a[i]; } int mid,ans; while(l<=r){ mid=(l+r)/2; int t=0,cnt=1; for(int i=1;i<=n;i++){ if(t+a[i]<=mid){ t+=a[i]; }else{ t=a[i]; cnt++; } } if(cnt>m){ l=mid+1; }else{ r=mid-1; ans=mid; } } cout<<ans; return 0; }