POJ 3273 Monthly Expense 二分

我们对每个月花费的最小花费进行二分，对于每一次二分的值mid，计算能花的月份数量，如果月份数量小于等于m，我们就不断的缩小mid，直到找到月份数量小于等于m 与 月份数量大于m的临界值，取最后一次满足条件的mid，输出即可。

#include <iostream>
using namespace std;
int arr[100007], n, m, maxt = 0;
void input()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){scanf("%d", &arr[i]);maxt = max(maxt, arr[i]);}
}
bool judge(int mid)
{int count = 0, current = mid;for (int i = 1; i <= n; i++){if (current == arr[i]){current = mid;count++;}else if (current < arr[i]){current = mid - arr[i];count++;}else{current = current - arr[i];}}if (current != mid){count++;}return count <= m;
}
void binarySearch()
{int left = maxt - 1, right = 1000000001;while (left + 1 < right){int mid = (left + right) / 2;if (judge(mid)){right = mid;}else{left = mid;}}printf("%d\n", right);
}
int main()
{input();binarySearch();return 0;
}