#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; 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[1001000],l=0,r=0,mid,ans; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; l=max(l,a[i]); r+=a[i];} while(l<=r){ mid=(l+r)/2; int sum=0,c=1; for(int i=1;i<=n;i++){ if(sum+a[i]<=mid){ sum+=a[i];} else { sum=a[i]; c++;}} if(c<=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; }

5 3 4 2 4 5 1