題干：

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤?moneyi?≤ 10,000) that he will need to spend each day over the next?N?(1 ≤?N?≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly?M?(1 ≤?M?≤?N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Line 1: Two space-separated integers:?N?and?M?
Lines 2..?N+1: Line?i+1 contains the number of dollars Farmer John spends on the?ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

7 5 100 400 300 100 500 101 400

Sample Output

500

Hint

If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.

題目大意：

給你一個長度為N的序列，現在需要把他們切割成M個子序列（所以每一份都是連續的），使得每個子序列和均不超過某個值X，輸出X的最小值。

換句話說，切成M份，然后每一份都有一個和sum[i]，其中最大的一個是maxSum = max(sum[i]),問這個最大值最小是多少？

?

解題報告：

? ? 剛開始讀題以為要加點貪心，后來發現是要切割數組，所以是連續的，不能排序、、、白白WA一發、、

AC代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define ll long long using namespace std; ll sum,a[100005]; ll n,m; bool ok(ll lim) {int cnt = 0;ll cur = 0;for(int i = 1; i<=n; i++) {if(cur + a[i] <= lim) {cur+= a[i];}else {cnt++;cur=0;i--;}}if(cnt >= m) return 0;else return 1; } int main() {cin>>n>>m;for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum += a[i]; // sort(a+1,a+n+1);ll l = *max_element(a+1,a+n+1),r = sum;ll mid = (l+r)/2;while(l < r) {mid = (l+r)/2;if(ok(mid)) r=mid;else l=mid+1; }printf("%lld\n",l);return 0 ;}

2020/1/29再做：

還是WA了一發，是因為下界寫成了0，其實不能是0，因為當l為特別小的值的時候有可能被認為合法。

比如這個樣例：

5 5
1 10000 3 4 5

如果你代碼這么寫，則會輸出1

或者采用這樣的方法避免修改下界。

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; typedef pair<int,int> PII; int n,k,a[MAX]; bool ok(ll x) {int cnt = 1; ll cur = 0;for(int i = 1; i<=n; i++) {if(cur + a[i] <= x) cur += a[i];else {cnt ++,cur = a[i];if(cur > x) return 0;}}return cnt <= k; } int main() {while(cin>>n>>k) {for(int i = 1; i<=n; i++) cin>>a[i];ll l = 0,r = 1e12,ans,mid;while(l<=r) {mid = (l+r)>>1;if(ok(mid)) r = mid - 1,ans = mid;else l = mid + 1;}printf("%lld\n",ans); }return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 3273 】Monthly Expense （二分，最小最大值）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。