POJ 3273 Monthly Expense——二分

POJ 3273 Monthly Expense——二分

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.

一开始用dp没思路，看了别人的博客后才知道这题要二分查找。

思路：

最大值随着区间的划分而改变，每次区间划分时我们难以确定应该分到什么程度，基于这个问题我们可以先计算出最大值的上限和下限， 然后在这个上下限确定的区间中二分查找满足题意的那个最大值。

对于每个mid（二分查找时的中值），我们都以他为最大值划分一次区间（区间数尽量小），然后将得到的区间数cnt与题目所给的区间数m进行比较，如果cnt < m，就说明最大值大了，导致划分的区间数小了，符合题意的最大值应该在下限left和mid为上限的区间中，所以另上限left变为mid，继续二分；反之同理。当某个mid值下划分的区间数恰好为m时，说明这个值可能时满足题意的最大值，我们还要考虑另结果最小，所以继续二分，另上限right为mid寻找更小的最大值，找到了就继续找更小的...没找到的话当前的区间数一定比题目中的m大，所以下限left会增加...直到下限>=上限时二分结束。

#include #include #include using namespace std;int main(){ int n, m; while (scanf("%d %d", &n, &m) == 2) { int a[n + 1]; int left = -1, right = 0;//二分上界和下界 for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); left = max(left, a[i]); right += a[i]; } //left是把每份钱划分为一个区间，right是把所有钱划分为一个区间 while (left < right) { int mid = (left + right) >> 1;//相当于/2 //计算在left为下界mid为上界的范围内最少可以划分多少个区间，保证每个区间的和小于mid上限 int cnt = 0;//区间数 int sum = 0;//每个区间的和 for (int i = 1; i <= n; i++) { if (sum + a[i] > mid) {//每个区间的和不能超越mid上限，所以在这里要划分区间，且区间不能包括a[i],所以让sum = a[i] cnt++; sum = a[i]; } else sum += a[i];//和不大于mid的话就继续累加，尽量让区间数小 } cnt++;//如果到n时sum的值恰好大于mid，那么需要把最后一份单独划分，如果没大于mid，就要把最后一段划分为一份，总之份数都要加一 if (cnt <= m) right = mid;//区间数少了说明上限取大了，区间数正好还是要进一步减小right以得到最小的结果 else left = mid + 1;//少了 +1 TLE了一次... } printf("%d\n", right); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。