月度开销
思路
给定连续N天的开销，需要将这些天分成M个财政周期，使得开销最多的财政周期的开销尽可能少。
首先，我们可以确定一个财政周期的长度l，即将N天平均分成M个财政周期。这样每个财政周期的长度就是N/M。
然后，我们需要计算每个财政周期中的开销总和。假设当前财政周期的起始位置为i，那么当前财政周期的开销总和就是从第i天开始的连续N/M天的开销之和，即SUM(i, i+N/M-1)。
接下来，我们需要找到开销总和最大的财政周期，即找到使得SUM(i, i+N/M-1)最大的i。
我们可以使用滑动窗口的思想来解决这个问题。首先，我们计算起始位置为0的财政周期的开销总和SUM(0, N/M-1)。然后，我们从左往右依次移动起始位置i，每次移动一个位置，将起始位置i-1的开销减去第i-1天的开销，再加上第i+N/M-1天的开销，即得到起始位置为i的财政周期的开销总和SUM(i, i+N/M-1)。我们将SUM(i, i+N/M-1)与原先的最大开销进行比较，如果大于最大开销，就更新最大开销。
最后，最大开销就是最大月度开销的最小值。
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, a[N];
bool check(int k) //在每个子段和小于等于k的情况下，最少的子段数量是否小于等于m
{//注意:a中的单独一个元素也可能大于k
int sum = 0, ct = 1;//sum：当前子段加和 ct：现在在看第几个子段
for(int i = 1; i <= n; ++i)
{
if(a[i] > k)//存在元素大于k，
return false;
if(sum + a[i] <= k)
sum += a[i];
else
{
ct++;//看下一子段
sum = a[i];//i作为下一子段的第一个元素
}
}
return ct <= m;
}
int main()
{
int tot = 0;//加和
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
tot += a[i];
}
int l = 0, r = tot, mid;//子段和最大值不会大过所有数的加和
while(l < r)//二分答案求满足某一条件的最小值
{
mid = (l + r) / 2;
if(check(mid))
r = mid;
else
l = mid + 1;
}
cout << l;
return 0;
}